学 院：班 级：完 成 人：姓指导教师：
数据结构课程设计
说 明 书
信息科学与工程学院 计算机11-2 名： 学 号： 201101050220 姓 名： 学 号： 201101050221
山 东 科 技 大 学 2012年12月13日
- 1 -
课 程 设 计 任 务 书
一、课程设计题目： 构造可以使n个城市连接的最小生成树
二、课程设计应解决的主要问题：
（1） 邻接矩阵的构造及其存储 （2） 判断是否能够生成最小生成树 （3） 克鲁斯算法的设计 （4） 利用克鲁斯算法构造最小生成树时是否产生回路的判断 （5） 界面的设计
三、任务发出日期： 2012-11-28 课程设计完成日期： 2012-12-13
- 2 -
小组分工说明
小组分工情况：
王 露：算法设计，void Kruskal()函数，void set ()函数，void find()函数，void Union()函数
王炜程：void creat()函数，void judge()函数，int main()函数；int menu()函数，void display()函数
组长签字： 年 月 日
小组编号 35 题 目： 构造可使n个城市连接的最小生成树
指导教师对课程设计的评价
成绩：
指导教师签字：
年 月 日
- 3 -
目录
二、
一、 主要问题------------------------------------------------------------------5
基本要求------------------------------------------------------------------5
三、 算法基本思想描述------------------------------------------------------5 四、 详细设计------------------------------------------------------------------5
1、数据结构的设计----------------------------------------- 5
<1> 存储结构------------------------------------------------------- 5
<2> 图的表示--------------------------------------------------------6
2、算法的设计---------------------------------------------6
<1> 克鲁斯卡尔算法设计----------------------------------------------6 <2> 防止不能构成最小生成树的图--------------------------------------6 <3> 模块结构及功能-------------------------------------------------- 7 <4> 主要模块算法描述------------------------------------------------ 7
五、源程序清单-----------------------------------------------------------------9 六、测试数据及测试结果-----------------------------------------------------9
1、开始画面--------------------------------------------------------- 9 2、输入信息--------------------------------------------------------- 10 3、数据处理--------------------------------------------------------- 10 （1）判断能否构成最小生成树--------------------------------------- 10 （2）遍历所有的最小生成树----------------------------------------- 10 （3）退出--------------------------------------------------------- 11
七、课程设计总结--------------------------------------------------------------11 八、附录--------------------------------------------------------------------------------11 参考书目--------------------------------------------------------------------------15
- 4 -
构造可以使n个城市连接的最小生成树
一、主要问题
给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。
二、基本要求
（1）城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城
市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。 （2）表示城市间距离网的邻接矩阵（要求至少6个城市，10条边） （3）最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。
三、算法基本思想描述
Kruskal算法思想基本描述：假设连通图N=（V，{E}），则令最小生成树的初始状态为只有n 个顶
点而无边的非连通图T=(V,{ })，图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。以此类推，直至T中所有顶点都在同一个连通分量上为止。
四、详细设计
1、 数据结构的设计
<1> 存储结构
邻接矩阵存储方法（数组存储方法），利用两个数组来存储一个图，其构造原理比较简单。
对于具有n个顶点的图G=(V,E),定义一个具有n个元素的一维数组VERTEX[0..n-1]，将图中顶点的数据信息分别存入该数组的一个数组元素中。另外，定义一个二维数组A[0..n-1][0..n-1],该二维数组通常被称为邻接矩阵。若以顶点在VERTEX数组中的下标来代表一个顶点，则邻接矩阵中元素A[i][j]存放顶点i到顶点j之间的关系信息，有
1
当顶点i与顶点j之间有边时
A[i][j] = 0 当顶点i与顶点j之间无边时
对于网络，有
- 5 -