发布时间 : 星期一 文章最小生成树的应用数据结构课程设计更新完毕开始阅读
摘 要
求一个网的最小生成树，即以最低的经济建设n个城市之间的通信网，利用普里姆算法和克鲁斯卡尔算法求这个网的最小生成树。
关键词：网的最小生成树；Kruskal算法；Prim算法；边和权值。
0
目 录
1 问题描述 ................................................................................................ 1 2 需求分析 ................................................................................................ 1 3 概要设计 ................................................................................................ 1 3．1抽象数据类型定义 ..................................................................... 1 3．2模块划分 ..................................................................................... 3 4 详细设计 ................................................................................................ 5 4．1数据类型的定义 ......................................................................... 5 4．2主要模块的算法描述 ................................................................. 5 5 测试分析 .............................................................................................. 13 6 课程设计总结 ...................................................................................... 13 参考文献 .................................................................................................. 16 附录（源程序清单） .............................................................................. 17
1
1 问题描述
若要在n个城市之间建设通信网络，只需要架设n-1条线路即可。如何以最低的经济建设这个通信网，是一个网的最小生成树。
2 需求分析
（1）.可以用连通网来表示n个城市间可能设置的通信网络，其中网的顶点表示城市，边表示两城市之间的路线，边的权值表示相应的费用。
对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。现在，我们要选择这样一棵生成树，它使总的费用最少，这棵树就是最小生成树。一棵生成树的费用就是树上各边的费用之和。
（2）.本程序的目的是要建设一个最经济的通信网，根据用户输入的网，输出相应的最小生成树。在这里城市以及两城市之间的费用都用整型数来代替。利用克鲁斯卡尔算法和普利姆算法实现。
3 概要设计
3．1抽象数据类型定义 1.ADT Graph
{ 数据对象V：v是具有相同特性的数据元素的集合，称为顶点集。 数据关系R：R={VR}
VR={
谓词p(v,w)定义了弧
基本操作：
(1) CreatGraph(&G,V,VR)；
初始条件：V是图的顶点集，VR是图中弧的集合。 操作结果：按V和VR的定义构造图G。
1
(2) LocateVex(G, u)；
初始条件：图G存在,u和G中顶点有相同的特征。
操作结果：若G中存在顶点u，则返回该顶点在图中的位置；否则返回
其他信息。
(3) DestoryGraph(&u)；
初始条件：图G存在。 操作结果：销毁图G。
(4) GetVex(G, v)；
初始条件：图G存在，v是图中某个顶点。 操作结果：返回v的值。
(5) NextAdjVex(G, v, w)；
初始条件：图G存在，v是图中某个顶点，w是v的邻接顶点。 操作结果：返回v的（相对于w的）下一个邻接顶点。若w是v的
最后一个邻接点，则返回“空”。
(6) BFSTraverse(G, Visit( ))；
初始条件：图G存在，Visit是顶点的应用函数。
操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点调用函数
Visit一次且仅一次。一旦visit( )失败，则操作失败。}
2. 存储结构 Typedef struct {
int adj;
2