2022年最小生成树实验报告.doc

2021年最小生成树实验报告
2021年最小生成树实验报告
1 / 9
2021年最小生成树实验报告
数据结构课程设计汇报
题目: 最小生成树问题
院（系）: 计算机工程学院
学生姓名:
班级: 学号:
起迄日期:
指导老师:
— 第 2 学期
一、 需求分析
2021年最小生成树实验报告
2021年最小生成树实验报告
2 / 9
2021年最小生成树实验报告
:
在n个城市之间建设网络, 只需确保连通即可, 求最经济架设方法。存放结构采取多个。求解算法多个。

在n个城市之间建设网络, 只需要架设n-1条线路, 建立最小生成树即可实现最经济架设方法。
程序可利用克鲁斯卡尔算法或prim算法生成最小生成树。

以文本形式输出最小生成树, 同时输出它们权值。经过人机对话方法即用户经过自行选择命令来输入数据和生成对应数据结果。
二、 概要设计
:
因为是最小生成树问题, 所以采取了书本上介绍过克鲁斯卡尔算法和
prim算法两种方法来生成最小生成树。依据要求, 需采取多个存放结构, 所
以我选择采取了邻接表和邻接矩阵两种存放结构。
:
图状结构:
ADT Graph{
数据对象V: V是含有相同特征数据元素集合, 称为顶点集。
数据关系R: R={VR}
VR={<v,w>|v,w∈V且P(v,w), <v,w>表示从v到w弧,
谓词P(v,w)定义了弧<v,w>意义或信息}
基础操作:
CreateGraph( &G, V, VR )
初始条件: V是图顶点集, VR是图中弧集合。
操作结果: 按V和VR定义结构图G。
DestroyGraph( &G )
初始条件: 图G存在。
操作结果: 销毁图G。
LocateVex( G, u )
初始条件: 图G存在, u和G中顶点有相同特征。
操作结果: 若G中存在顶点u, 则返回该顶点在图中位置; 不然返
回其它信息。
GetVex( G, v )
初始条件: 图G存在, v是G中某个顶点。
2021年最小生成树实验报告
2021年最小生成树实验报告
3 / 9
2021年最小生成树实验报告
操作结果: 返回v值。
PutVex( &G, v, value )
初始条件: 图G存在, v是G中某个顶点。
操作结果: 对v赋值value。
FirstAdjVex( G, v )
初始条件: 图G存