最小生成树的课程设计

1、精品资料SHENYANG UNIVERSITY OF TECHNOLOGY数据结构与算法课程设计报告课程设计题目：构造可以使n个城市连接的最小牛成树专业班级：信息与计算科学1001班姓 名： 学 号:设计室号:理学院机房精品资料设计时间：2011-12-26批阅时间：指导教师：成绩：构造可以使n个城市连接的最小生成树主要任务：给定一个地区的 n n 个城市间的距离网，用 PrimPrim 算法或 KruskalKruskal 算法建立最 小生成树，并计算得到的最小生成树的代价。设计该程序的基本要求：1 1、城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本 中给出的定义，若两个城市

2、之间不存在道路，则将相应边的权值设为自己定义 的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路， 并显示得到的最小生成树的代价。2 2、表示城市间距离网的邻接矩阵（要求至少 6 6 个城市，1010 条边）3 3、最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。总体设计设计室号:理学院机房精品资料1 1该程序的主要功能：能实现根据输入城市的信息可以判断该城市间的距离网是否构成最小生成树，遍历城市生成最小生成树，通过计算得到最小生成 树的代价。2 2该城市间的距离网用邻接矩阵表示3 3用克鲁斯卡尔（KruskalKruskal ）算法建立最小生成树详细设计说明1

3、1该程序的主要功能：能实现根据输入城市的信息可以判断出该城市间的距 离网是否构成最小生成树，遍历城市生成最小生成树，通过计算得到最小生成树 的代价。该程序的模块结构功能图及主要函数如下：精品资料精品资料a)a)intintmaimai n n ()()/主程序b)b)intintmenumenu ()()/菜单函数c)c)voidvoidcreatecreate ()()输入城市信息函数d)d)voidvoidjudgejudge ()()判断是否能够生成最小生成树函数e)e)voidvoiddisplay()display()/打印输出f)f)voidvoidsetset ()()初始化 p

4、re,rankpre,rank函数g)g)voidvoidfindfind ()()判断是否构成回路函数h)h)voidvoidUnUn ioio n n ()()将能构成最小生成树的边添加到一个集合1 1)voidvoidKrushal()Krushal()/克鲁斯算法求最小生成树体会确定程序功能设计出总体流程对整个设计进行非常重要， 明确要完成设计需要的 程序算法，为整个设计流程划出大纲，可以使整个设计思路更加简单明了。2 2构造结构体本题为求最小生成树，先要构造一个结构体，再用邻接矩阵的形式表现出来。#defi ne max 20#defi ne MAXLNT 10精品资料typedef

5、 struct node /*构造一个结构体，两个城市可以看成起点和终点，之间的道路可以看 成一个边*/int str; /* 起点 */int end; /* 终点 */int dis;/* 距离 */n ode;node pmax,temp;/*p 记录城市信息 */int pre100,ra nk100;/* 用于判断是否构成回路*/int n=O,arcsMAX_LNTMAX_LNT;/* n表示城市个数,3 3初始化void set(int x)/* 初始化 */prex = x;ran kx = 0;int find(int x)/*找到这个点的祖先*/arcs记录城市间权值*/精

6、品资料if(x != prex)prex = fin d(prex);return prex;void Union (i nt x,int y)/* 将这两个添加到一个集合里去*/x = fin d(x);y = fin d(y);if(ra nkx= ran ky)prey = x;ran kx +;else prey = x;该城市间的距离网使用邻接矩阵表示，邻接矩阵存储方法(数组存储方法)，利用两个数组来存储一个图。用 aa ii jj数组，利用邻接矩阵方式来储存城市与城市 间信息。void create( )/*输入城市信息*/精品资料int i,j;printf(请输入城市的个数：n

7、);scan f(%d, &n);printf(输入%d 个城市的邻接矩阵：n,n);for(i = 1;i = n;i +)for(j = 1;j = n;j +)scan f(%d, &arcsij);3 3算法设计(1) 克鲁斯卡尔算法思想基本描述：假设连通图 N=N=(V V，EE)，则令最小生成树的初始状态为只有 n n 顶点而无 边的非连通图 T=(V,T=(V, )，图中每个顶点自成一个连通分量。在 E E 中选择代价最 小的边，若该边依附的顶点落在 T T 中不同的连通分量上，则将此边加入到 T T 中, 否则舍去此边而选择下一条代价最小的边。以此类推，直至T

8、T 中所有顶点都在同一个连通分量上为止。(2) 克鲁斯卡尔算法设计a.a. 设置计数器 E E，初值为 0 0，记录已选中的边数。将所有边从小到大排序，存于 PP中。b.b. 从 pp中选择一条权值最小的边，检查其加入到最小生成树中是否会构成回精品资料路，若是，则此边不加入生成树；否则，加入到生成树中，计数器 E E 累加 1 1c.c. 从 E E 中删除此最小边，转d.d. 判断是否构成回路的方法：void Kruskal( )int ans = O,i,j,k = 0;int in dex;int count = 0;for(i = 1;i = n;i +)set(i);for(i =

9、1;i = n;i +)for(j = i + 1;j = n;j +)p+k.str = i;pk.e nd = j;pk.dis = arcsij; /*b b 继续执行，直到 k=n-1,k=n-1,算法结束/*ans 用来记录生成最小树的权总值*/*记录打印边的条数*/* 初始化数组 prex,rankx*/先把所有城市之间的路段看成一个边*/for(i=1;i=k;i+)/*把所有的边按从小到大进行排序*/in dex=i;精品资料for(j=i+1;j=k;j+) if(pj.dis pi ndex.dis)in dex=j;temp=pi ndex;pi ndex=pi;pi=t

10、emp;for(i = 1;i = k;i +)if(fin d(pi.str) != fin d(pi.e nd)/* 如果这两点连接在一起不构成一个回路，则执行下面操作*/printf(t 第 %d 条路段为：d-%d,权值为 %dn,+coun t,pi.str,pi.e nd,pi.dis);/*将这条边的起点、终点打印出来*/ans += pi.dis;/*说明这条路段要用*/Union( pi.str,pi.e nd);printf(t 遍历所有城市得到最小生成树的代价为：%dnn,ans);精品资料设置集合 S S，其中存放已加入到生成树中的边所连接的顶点集合，当一条新的边要加入

11、到生成树中时，检查此边所连接的两个顶点是否都已经在S S 中，若是则表示构成回路，否则，若有一个顶点不在S S 中 或者两个顶点都不在 S S 中,则不够成回路。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 +)int min = 10000000

12、0,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);elseprintf(”能构成最小生成树n);克鲁斯卡尔算法(Kruskals algorithm)是两个经典的最小生成树算法的较为简单理解的一个。这里面充分体现了贪心算法的精髓。精品资料克鲁斯卡尔算法生成最小生成树的过程(3 3

13、 )防止不能构成最小生成树的图为避免输入的图构成的不是连通图，设计了 judgejudge ()()函数来判断输入数据 构成的是否为连通图，此函数的主要算法是源于普里姆( PRIMPRIM )算法，经过改 编，形成了新的函数。4主函数的设计int main()/*主函数 */while(1)switch( menu( )case 1:create( );break;/* 输入城市信息 */case 2:judge( );break;/*判断是否能够生成最小生成树*/精品资料case 3:display( );break;/*显示生成的最小生成树*/case 4:exit( 0 );精品资料re

14、turn 0;调试与测试网络图GE162019odA16O011CO652011od2214 QO19cd22018oOod61418od9V509y邻接矩阵精品资料生成界面. 20111229 3 . .求最小生成树请输入所选功百別-4输入城市间信息43权S S i i自s st t取信一成ES市之leKn有替帰U U 1 12 2 3 3 4 4精品资料20111229 0求最小生成树请输人所选功冃也-4詁输入城市的个数=.20111229 0.求最小生成树请输入所选功月也 Y请输入城市的个数醫為入石个城市的邻接矩阵：S4枫I I艺成T生亲信一成间构帀1 1市否有入断历岀WWSWWS121

15、2 3 3 4 41 12 2 3 3 4 4树尘息公胶信一成间构、帀之鬣帀否有入卧历出.二刖目精品资料I月输入所选功能4器输入城市的个数： 爲入石个城市的邻接矩阵：10006 16 28 9 10030 1000016 10000 11 10000 6 528 11 10000 22 14 1000019 10000 22 10000 1S 1000010000 6 14 18 10000 910000石10800 10800 9 10000.20111229 0.判断是否生成最小生成树.2011122?t求最小生成树请输入所选功能4曜构成最小生成樹遍历所有城市最小生成树主成尘意个最信一成S

16、 S H H间构市之市否有入断历岀H H 1 12 2 3 34 4丿-K-一自5-01販信一fifo间构市帀否有入断历岀1 12 2 3 3 4 4翻树精品资料求最小生成树请输入所选功能4. 201112 029日.退出求取小生成树请输入所选功冃也 Ti?ess antj key七o con七:inuE：程序源代码#in elude #in elude #i nclude 生成息个-最信-成的成生、帀否有替需入断历出H H1 16 6 8 85 56 6 111111枢为为为为高a affilalffiffilalffi亠土SISSIS# # * * * * * * LaLa显6 65 5

17、3 3 2 2 S SE E3 3一E级z z L L至2 2 2 2 2 2 1 1 4 4 1 1 3 3 1 1为为为为为妬! !- -Q Qi i一-二nKnKQ Qi i二-r*r*一3J3JD DT TK Kn ni i n nT TK Kn ni in ni iK K1 12 2 3 3 4 4 5 5 H H第第第第電主成尘最八息个最信晟间构帀、帀否荷入断历出H H1212 3 3 4 4精品资料#defi nemax 20#defi neMAX_LNT 10typedef struct node /* 构造一个结构体，两个城市可以看成起点和终点，之间的道路可以看 成一个边*/

18、int str; /* 起点 */int end; /* 终点 */int dis;/* 距离 */n ode;node pmax,temp;/*p 记录城市信息 */int pre100,ra nk100;/* 用于判断是否构成回路 */intn=0,arcsMAX_LNTMAX_LNT;/*n表示城市个数，arcs记录城市间权值 */int menu（ ）/*菜单函数 */int m;printf（.2011年 12 月 29 日.nn）;printf（求最小生成树n）;精品资料printf(”nn);printf(”1输入城市之间的信息n);printf(”2判断是否能构成一个最小生成树

19、n);printf(”3遍历所有城市生成最小生成树n);printf(”4退出n);printf(”nn);printf(”请输入所选功能 1-4n);system(color A);/*改变界面颜色的，对程序没什么影响*/scan f(%d,&m);return m;/*下面三个函数作用是检验当一条边添加进去，是否会产生回路*/void set(int x)/* 初始化 */prex = x;ran kx = 0;int find(int x)/*找到这个点的祖先*/精品资料精品资料if(x != prex)prex = fin d(prex);return prex;void Un

20、ion (i nt x,int y)/* 将这两个添加到一个集合里去x = fin d(x);y = fin d(y);if(ran kx = ran ky)prey = x;ran kx +;else prey = x;void Kruskal( )int in dex;*/int ans = O,i,j,k = 0;/*ans用来记精品资料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.st

21、r = i;pk.e nd = j;pk.dis = arcsij; /*先把所有城市之间的路段看成一个边*/for(i=1;i=k;i+)/*把所有的边按从小到大进行排序*/in dex=i;for(j=i+1;j=k;j+) if(pj.dis pi ndex.dis)in dex=j;temp=pi ndex;pi ndex=pi;pi=temp;for(i = 1;i = k;i +)if(fin d(pi.str) != fin d(pi.e nd)/* 如果这两点连接在一起不构成一个回路,则执精品资料行下面操作*/printf(t第 %d 条路段为：d-%d,权值为dn,+coun

22、 t,pi.str,pi.e nd,pi.dis);/*将这条边的起点、终点打印出来*/ans += pi.dis;/*说明这条路段要用*/Union( pi.str,pi.e nd);printf(t 遍历所有城市得到最小生成树的代价为：%dnn,ans);void create( )/*输入城市信息*/int i,j;printf(请输入城市的个数:n);scan f(%d, &n);printf(输入%d 个城市的邻接矩阵:n,n);for(i = 1;i = n;i +)for(j = 1;j = n;j +)scan f(%d, &arcsij);精品资料void display( )/*显示生成的最小