《广工数据结构课程设计最小生成树.pdf》由会员分享，可在线阅读，更多相关《广工数据结构课程设计最小生成树.pdf（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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;/*用于判断是否构成回路*/int n=0,arcsMAX_LN
3、TMAX_LNT;/*n 表示城市个数，arcs记录城市间权值*/主程序流程如下：.3.详细设计 （1）克鲁斯卡尔算法思想基本描述：假设连通图 N=（V，E），则令最小生成树的初始状态为只有 n 顶点而无边的非连通图 T=(V,)，图中每个顶点自成一个连通分量。在 E 中选择代价最小的边，若该边依附的顶点落在 T 中不同的连通分量上，则将此边加入到 T 中，否则舍去此边而选择下一条代价最小的边。以此类推，直至 T 中所有顶点都在同一个连通分量上为止。（2）克鲁斯卡尔算法设计：a.设置计数器 E，初值为 0，记录已选中的边数。将所有边从小到大排序，存于 p 中。b.从 p 中选择一条权值最小的边
4、，检查其加入到最小生成树中是否会构成回路，若是，则此边不加入生成树；否则，加入到生成树中，计数器 E 累加 1。c.从 E 中删除此最小边，转 b 继续执行，直到 k=n-1,算法结束。判断是否回路：设置集合 S，其中存放已加入到生成树中的边所连接的顶点集合，当一条新的边要加入到生成树中时，检查此边所连接的两个顶点是否都已经在 S 中，若是，则表示构成回路，否则，若有一个顶点不在 S 中 或者两个顶点都不在 S 中，则不够成回路。/*需要的函数声明*/int main()/主程序 int menu()/菜单函数 void create()/输入城市信息函数 void judge()/判断是否能
5、够生成最小生成树函数 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);printf(1 输入城市之间的信息n);printf(2 判断是否能构成一个最小生成树n);printf(3 遍历所有城市生成最小生成树n);printf(0
6、退出n);printf(_nn);printf(请输入所选功能 0-3n);scanf(%d,&m);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 =ranky)prey=x;rankx+
7、;else prey=x;/*克鲁斯算法求最小生成树*/void Kruskal()int ans=0,i,j,k=0;/*ans 用来记录生成最小树的权总值*/int index;int count=0;/*记录打印边的条数*/for(i=1;i=n;i+)/*初始化数组 prex,rankx*/set(i);for(i=1;i=n;i+)for(j=i+1;j=n;j+)p+k.str=i;pk.end=j;pk.dis=arcsij;/*先把所有城市之间的路段看成一个边*/.for(i=1;i=k;i+)/*把所有的边按从小到大进行排序*/index=i;for(j=i+1;j=k;j+
8、)if(pj.dis pindex.dis)index=j;temp=pindex;pindex=pi;pi=temp;for(i=1;i=k;i+)if(find(pi.str)!=find(pi.end)/*如果这两点连接在一起不构成一个回路，则执行下面操作*/printf(t第%d条路段为：%d-%d,权值为%dn,+count,pi.str,pi.end,pi.dis);/*将这条边的起点、终点打印出来*/ans+=pi.dis;/*说明这条路段要用*/Union(pi.str,pi.end);printf(t 遍历所有城市得到最小生成树的代价为:%dnn,ans);/*输入城市信息*
9、/void create()int i,j;printf(请输入城市的个数（130）:n);scanf(%d,&n);if(n30)printf(输入错误，请重新输入n);return;printf(输入%d 个城市存储边(带权)的数组（数值范围：1-99，用 100 表.示，）:n,n);for(i=1;i=n;i+)for(j=1;j=n;j+)scanf(%d,&arcsij);if(arcsij100)printf(输入错误，请重新输入n);return;for(i=0;in;i+)for(j=0;ji;j+)if(arcsij!=arcsji)/*判断矩阵是否对称*/printf(输
10、入错误，请重新输入n);return;/*显示生成的最小生成树*/void display()if(n=0)printf(这里没有城市之间的信息n);return;printf(遍历所有城市得到最小生成树为：nnn);Kruskal();./*判断是否能够生成最小生成树*/void judge()int close100,low100,i,j,ans=0;/*closej表示离 j 最近的顶点，lowj表示离 j最短的距离*/int use100;use1=1;for(i=2;i=n;i+)lowi=arcs1i;/*初始化*/closei=1;usei=0;for(i=1;i n;i+)in
11、t min=100000000,k=0;for(j=2;j 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;/*判断是否能够
12、生成最小生成树*/case 3:display();break;/*显示生成的最小生成树*/case 0:exit();default:printf(输入错误，请重新选择。n);break;4.调试分析 本课程设计重点在于生成最小生成树算法。克鲁斯卡尔算法将图中边按其权值由小到大的次序顺序选取,若选边后不形成回路,则保留作为一条边,若形成回.路则除去，依次选够(n-1)条边,即得最小生成树。在克鲁斯卡尔算法中，图的存贮结构采用边集数组,且权值相等的边在数组中排列次序可以是任意的，该方法对于边相对比较多的不是很实用。本课程设计为求最小生成树，先要构造一个结构体，再用邻接矩阵的形式表现出来。城市间
13、的距离网使用邻接矩阵表示，邻接矩阵存储方法（数组存储方法），利用两个数组来存储一个图。用 a i j数组，利用邻接矩阵方式来储存城市与城市间信息。5.用户使用说明 按顺序依次输入城市之间的信息，判断是否能构成一个最小生成树，再生成遍历所有城市的最小生成树。如果输入过程中出现错误，需重新输入。城市存储边(带权)矩阵中的用 100 表示，矩阵必须对称。6.测试结果 7.源代码#include#include#include#define max 100#define MAX_LNT 30 typedef struct node/*构造一个结构体，两个城市可以看成起点和终点，之间的道路可以 看成一个
14、边*/int str;/*起点*/int end;/*终点*/int dis;/*距离*/node;.node pmax,temp;/*p 记录城市信息*/int 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 遍历所
15、有城市生成最小生成树n);printf(0 退出n);printf(_nn);printf(请输入所选功能 0-3n);scanf(%d,&m);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
16、 =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=n;i+)/*初始化数组 prex,rankx*/set(i);for(i=1;i=n;i+)for(j=i+1;j=n;j+)p+k.str=i;pk.end=j;.pk.dis=arcsij;/*先把所有城市之间的路段看成一个边*/for(i=1;i=k;i+)/*把所有的边按从小到大进行排序*/ind
17、ex=i;for(j=i+1;j=k;j+)if(pj.dis pindex.dis)index=j;temp=pindex;pindex=pi;pi=temp;for(i=1;i=k;i+)if(find(pi.str)!=find(pi.end)/*如果这两点连接在一起不构成一个回路，则执行下面操作*/printf(t第%d条路段为：%d-%d,权值为%dn,+count,pi.str,pi.end,pi.dis);/*将这条边的起点、终点打印出来*/ans+=pi.dis;/*说明这条路段要用*/Union(pi.str,pi.end);printf(t 遍历所有城市得到最小生成树的代价
18、为:%dnn,ans);/*输入城市信息*/void create()int i,j;printf(请输入城市的个数（130）:n);scanf(%d,&n);.if(n30)printf(输入错误，请重新输入n);return;printf(输入%d 个城市存储边(带权)的数组（数值范围：1-99，用 100 表示，）:n,n);for(i=1;i=n;i+)for(j=1;j=n;j+)scanf(%d,&arcsij);if(arcsij100)printf(输入错误，请重新输入n);return;for(i=0;in;i+)for(j=0;ji;j+)if(arcsij!=arcsji
19、)/*判断矩阵是否对称*/printf(输入错误，请重新输入n);return;/*显示生成的最小生成树*/void display()if(n=0)printf(这里没有城市之间的信息n);return;.printf(遍历所有城市得到最小生成树为：nnn);Kruskal();/*判断是否能够生成最小生成树*/void judge()int close100,low100,i,j,ans=0;/*closej表示离 j 最近的顶点，lowj表示离 j最短的距离*/int use100;use1=1;for(i=2;i=n;i+)lowi=arcs1i;/*初始化*/closei=1;use
20、i=0;for(i=1;i n;i+)int min=100000000,k=0;for(j=2;j 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;