《广工数据结构课程设计最小生成树.pdf》由会员分享，可在线阅读，更多相关《广工数据结构课程设计最小生成树.pdf（17页珍藏版）》请在三一文库上搜索。
1、课程设计 课程名称数据结构 学院 专业班级 学号 学生姓名 指导教师 2015 年 7 月 2 日 1. 需求分析 题目：最小生成树问题 若要在 n 个城市之间建设通讯网络，只需要架设n-1 条线路即可。如何以最 低的经济代价建设这个通讯网，是一个网的最小生成树问题。 要求： （1）利用克鲁斯卡尔算法求网的最小生成树。 （2）实现并查集。以此表示构造生成树过程中的连通分量。 （3）以文本形式输出生成树中各条边以及他们的权值。 输入的形式和输入值的范围：十进制数，0100。 输出的形式：十进制数。 程序所能达到的功能：遍历所有城市生成最小生成树。 测试数据： 正确数据： 城市个数 3；3 个城市
2、的邻接矩阵： (1,2,3;2,100,4;3,4,6) 输出结果：第 1 条路段为 12，权值为 2 第 2 条路段为 13，权值为 3 遍历所有城市得到最小生成树的代价为：5 错误数据：城市个数3；城市的邻接矩阵： (-2,5,1;3,0,1;3,2,1) 输出结果：输入错误，请重新输入 2.概要设计 数据类型定义如下： typedef struct node int str; /*起点*/ int end; /*终点*/ int dis;/*距离*/ node; node pmax,temp; /*p 记录城市信息 */ int pre100,rank100;/* 用于判断是否构成回路
3、*/ int n=0,arcsMAX_LNTMAX_LNT;/*n表示城市个数， arcs记录城市间 权值*/ 主程序流程如下： 3.详细设计 （1）克鲁斯卡尔算法思想基本描述： 假设连通图 N=（V，E ），则令最小生成树的初始状态为只有n 顶点而无 边的非连通图T=(V, ) ，图中每个顶点自成一个连通分量。在E 中选择代价最 小的边，若该边依附的顶点落在T 中不同的连通分量上，则将此边加入到T 中， 否则舍去此边而选择下一条代价最小的边。以此类推，直至T 中所有顶点都在 同一个连通分量上为止。 （2）克鲁斯卡尔算法设计： a. 设置计数器 E，初值为 0，记录已选中的边数。将所有边从小到
4、大排序， 存于 p 中。 b. 从 p 中选择一条权值最小的边，检查其加入到最小生成树中是否会构成 回路，若是，则此边不加入生成树；否则，加入到生成树中，计数器E 累加 1。 c. 从 E 中删除此最小边，转b 继续执行，直到 k=n-1, 算法结束 。 判断是否回路： 设置集合 S，其中存放已加入到生成树中的边所连接的顶点集合，当一条新 的边要加入到生成树中时， 检查此边所连接的两个顶点是否都已经在S中， 若是， 则表示构成回路，否则，若有一个顶点不在S 中或者两个顶点都不在S中，则 不够成回路。 /*需要的函数声明 */ int main ( ) /主程序 int menu ( ) /菜单
5、函数 void create ( ) /输入城市信息函数 void judge ( ) /判断是否能够生成最小生成树函数 void display( ) /打印输出 void set ( ) /初始化 pre,rank函数 void find ( ) /判断是否构成回路函数 void Union ( ) /将能构成最小生成树的边添加到一个集合 void Krushal( ) /克鲁斯算法求最小生成树 /*菜单函数 */ int menu( ) int m; printf(“2015年 7 月 2 日nn“); printf(“ 求最小生成树 n“); printf(“ _nn“); print
6、f(“ 1 输入城市之间的信息 n“); printf(“ 2 判断是否能构成一个最小生成树n“); printf(“ 3 遍历所有城市生成最小生成树n“); printf(“ 0 退出n“); printf(“ _nn“); printf(“ 请输入所选功能 0-3n“); scanf(“%d“, if(m3) return 4; return m; /*下面三个函数作用是检验当一条边添加进去，是否会产生回路*/ void set(int x)/* 初始化 */ prex = x; rankx = 0; /*找到这个点的祖先 */ int find(int x) if(x != prex)
7、prex = find(prex); return prex; /*将这两个数添加到一个集合里去*/ void Union(int x,int y) x = find(x); y = find(y); if(rankx = ranky) prey = x; rankx +; else prey = x; /*克鲁斯算法求最小生成树*/ void Kruskal( ) int ans = 0,i,j,k = 0; /*ans 用来记录生成最小树的权总值*/ int index; int count = 0; /*记录打印边的条数 */ for(i = 1;i 30) printf(“ 输入错误，
8、请重新输入 n“);return ; printf(“ 输入 %d 个城市存储边 (带权 )的数组（数值范围：1-99，用 100 表 示，） :n“,n); for(i = 1;i 100) printf(“ 输入错误，请重新输入 n“); return ; for(i=0;i lowj)/*找到最小的 low 值，并记录 */ min = lowj; k = j; for(j = 2;j arcskj) lowj = arcskj; /* 修改 low 值和 close值*/ closej = k; ans += arcsclosekk; if(ans = 100000000) print
9、f(“ 不能构成最小生成树 n“); else printf(“ 能构成最小生成树 n“); /*主函数 */ void main() while(1) switch( menu( ) ) case 1:create( );break;/* 输入城市信息 */ case 2:judge( );break;/* 判断是否能够生成最小生成树*/ case 3:display( );break; /* 显示生成的最小生成树 */ case 0:exit( ); default: printf(“ 输入错误，请重新选择。n“); break; 4.调试分析 本课程设计重点在于生成最小生成树算法。克鲁斯
10、卡尔算法将图中边按其权 值由小到大的次序顺序选取,若选边后不形成回路,则保留作为一条边 ,若形成回 路则除去，依次选够 (n-1)条边 ,即得最小生成树。在克鲁斯卡尔算法中，图的存 贮结构采用边集数组 ,且权值相等的边在数组中排列次序可以是任意的，该方法 对于边相对比较多的不是很实用。 本课程设计为求最小生成树， 先要构造一个结构体， 再用邻接矩阵的形式表 现出来。 城市间的距离网使用邻接矩阵表示， 邻接矩阵存储方法（数组存储方法）， 利用两个数组来存储一个图。 用 a i j 数组，利用邻接矩阵方式来储存城市与城 市间信息 。 5.用户使用说明 按顺序依次输入城市之间的信息，判断是否能构成一
11、个最小生成树，再生成 遍历所有城市的最小生成树。 如果输入过程中出现错误， 需重新输入。 城市存储 边(带权)矩阵中的 用 100表示，矩阵必须对称。 6.测试结果 7. 源代码 #include #include #include #define max 100 #define MAX_LNT 30 typedef struct node /*构造一个结构体，两个城市可以看成起点和终点，之间的道 路可以 看成一个边 */ int str; /* 起点*/ int end; /*终点*/ int dis;/* 距离*/ node; node pmax,temp; /*p 记录城市信息 */ i
12、nt pre100,rank100;/* 用于判断是否构成回路 */ int n=0,arcsMAX_LNTMAX_LNT;/*n表示城市个数， arcs记录城市间权值 */ int menu( ) /*菜单函数 */ int m; printf(“2015年 7 月 2 日nn“); printf(“ 求最小生成树 n“); printf(“ _nn“); printf(“ 1 输入城市之间的信息 n“); printf(“ 2 判断是否能构成一个最小生成树n“); printf(“ 3 遍历所有城市生成最小生成树n“); printf(“ 0 退出n“); printf(“ _nn“);
13、printf(“ 请输入所选功能 0-3n“); scanf(“%d“, if(m3) return 4; return m; /*下面三个函数作用是检验当一条边添加进去，是否会产生回路*/ void set(int x)/* 初始化 */ prex = x; rankx = 0; int find(int x)/* 找到这个点的祖先 */ if(x != prex) prex = find(prex); return prex; void Union(int x,int y)/* 将这两个添加到一个集合里去*/ x = find(x); y = find(y); if(rankx = ran
14、ky) prey = x; rankx +; else prey = x; /*克鲁斯算法求最小生成树*/ void Kruskal( ) int ans = 0,i,j,k = 0; /*ans 用来记录生成最小树的权总值*/ int index; int count = 0; /*记录打印边的条数 */ for(i = 1;i 30) printf(“ 输入错误，请重新输入 n“);return ; printf(“ 输入 %d 个城市存储边 (带权 )的数组（数值范围：1-99，用 100 表 示，） :n“,n); for(i = 1;i 100) printf(“ 输入错误，请重新输
15、入 n“); return ; for(i=0;i lowj)/*找到最小的 low 值，并记录 */ min = lowj; k = j; for(j = 2;j arcskj) lowj = arcskj; /* 修改 low 值和 close值*/ closej = k; ans += arcsclosekk; if(ans = 100000000) printf(“ 不能构成最小生成树 n“); else printf(“ 能构成最小生成树 n“); /*主函数 */ void main() while(1) switch( menu( ) ) case 1:create( );break;/* 输入城市信息 */ case 2:judge( );break;/* 判断是否能够生成最小生成树*/ case 3:display( );break; /* 显示生成的最小生成树 */ case 0:exit( 0 ); default: printf(“ 输入错误，请重新选择。n“); break;