最小生成树地课程设计

1、SHENYANG UNIVERSITY OF TECHNOLOGY数据结构与算法课程设计报告课程设计题目：构造可以使n个城市连接的最小牛专业班级：成树信息与计算习科学1001班姓名：学号：设计室号：理学院机几房设计时间：2011-12-26批阅时间：指导教师：成绩：构造可以使n个城市航 车接的最小生成树主要任务：给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最 小生成树，并计算得到的最小生成树的代价。设计该程序的基本要求：1、城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本 中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义 的无穷大值

2、。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路， 并显示得到的最小生成树的代价。2、表示城市间距离网的邻接矩阵（要求至少 6个城市，10条边）3、最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。总体设计1该程序的主要功能：能实现根据输入城市的信息可以判断该城市间的距 离网是否构成最小生成树，遍历城市生成最小生成树，通过计算得到最小生成树 的代价。2该城市间的距离网用邻接矩阵表示3用克鲁斯卡尔（Kruskal）算法建立最小生成树详细设计说明1该程序的主要功能：能实现根据输入城市的信息可以判断出该城市间的距 离网是否构成最小生成树，遍历城市生成最小生成树，通过计算得到最小生

3、成树 的代价。该程序的模块结构功能图及主要函数如下:a)intmain ()主程序b)intmenu ()/菜单函数c)voidcreate ()输入城市信息函数d)voidjudge ()判断是否能够生成最小生成树函数e)voiddisplay()/打印输出f)voidset ()/初始化pre,rank函数g)voidfind ()判断是否构成回路函数h) void Union ( )/将能构成最小生成树的边添加到一个集合l ) void Krushal( )/克鲁斯算法求最小生成树体会确定程序功能设计出总体流程对整个设计进行非常重要， 明确要完成设计需要的 程序算法，为整个设计流程划出大

4、纲，可以使整个设计思路更加简单明了。2构造结构体 本题为求最小生成树，先要构造一个结构体，再用邻接矩阵的形式表现出来。#define max 20#define MAX_LNT 10typedef struct node /* 构造一个结构体，两个城市可以看成起点和终点，之间的道路可以看成 一个边 */int str; /* 起点 */int end; /* 终点 */int dis;/* 距离 */node;node pmax,temp;/*p 记录城市信息 */int pre100,rank100;/* 用于判断是否构成回路 */int n=0,arcsMAX_LNTMAX_LNT;/*n

5、表示城市个数， arcs 记录城市间权值 */3初始化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 +;else prey = x;该城市间的距离网使用邻接矩阵表示，邻接矩阵存储方法(数组存储方法) ，利 用两个

6、数组来存储一个图。 用 a i j 数组，利用邻接矩阵方式来储存城市与城市 间信息 。void create( )/* 输入城市信息 */int i,j;printf(" 请输入城市的个数 :n"); scanf("%d",&n);printf(" 输入 %d 个城市的邻接矩阵 :n",n);for(i = 1;i <= n;i +)for(j = 1;j <= n;j +) scanf("%d",&arcsij); 3 算法设计( 1) 克鲁斯卡尔算法思想基本描述 ：假设连通图 N=(

7、V ，E )，则令最小生成树的初始状态为只有 n 顶点而无 边的非连通图 T=(V, ) ，图中每个顶点自成一个连通分量。在 E 中选择代价最 小的边，若该边依附的顶点落在 T中不同的连通分量上，则将此边加入到T中,否则舍去此边而选择下一条代价最小的边。以此类推，直至T中所有顶点都在同 一个连通分量上为止 。(2)克鲁斯卡尔算法设计a. 设置计数器E,初值为0,记录已选中的边数。将所有边从小到大排序，存 于 p 中。b. 从 p 中选择一条权值最小的边，检查其加入到最小生成树中是否会构成回 路，若是，则此边不加入生成树；否则，加入到生成树中，计数器 E累加1。c. 从E中删除此最小边，转b继续

8、执行，直到k=n-1,算法结束d. 判断是否构成回路的方法：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(

9、i=1;i<=k;i+)/* 把所有的边按从小到大进行排序 */ index=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.d

10、is);/* 将这条边的起点、终点打印出来 */ans += pi.dis;/* 说明这条路段要用 */Union(pi.str,pi.end);printf("t 遍历所有城市得到最小生成树的代价为 : %dnn",ans);设置集合S,其中存放已加入到生成树中的边所连接的顶点集合，当一条新的 边要加入到生成树中时，检查此边所连接的两个顶点是否都已经在 S 中，若是 则表示构成回路，否则，若有一个顶点不在 S中 或者两个顶点都不在S中, 则不够成回路。void judge( )/* 判断是否能够生成最小生成树 */int close100,low100,i,j,ans =

11、 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 = 100000000,k = 0;for(j = 2;j <= n;j +)if(usej = 0 && min > lowj)/* 找到最小的 low 值，并记录 */min = lowj; k = j;for(j = 2;j <= n

12、;j +)if(usej = 0 && lowj > arcskj)Iowj = arcskj; /* 修改 low值和 close值 */ closej = k;ans += arcsclosekk;if(ans >= 100000000)printf(" 不能构成最小生成树 n");elseprintf(" 能构成最小生成树 n"); 克鲁斯卡尔算法 (Kruskal's algorithm) 是两个经典的最小生成树算法的较为简单理解的 一个。这里面充分体现了贪心算法的精髓。克鲁斯卡尔算法生成最小生成树的过程(3)

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

14、判断是IBJ 构 帀求最小生咸树请输入所选功能IF输入城市间信息2请输入所选功能丄-42仙1久年12月29日求最小生成树请输入城吊的个数=2P"年丄2月29日求最小生成树请输入所选功能4谙输入城市的个数；爲入&个城市的邻犊矩阵：JJi生成尘信一成将帀之專币否有入断历出芻碉退请输入所选功能I:青输入城市的个数； 跖入H个城市的邻接矩阳10309 IB ZEI 19 10938 10000It 10000 11 1(9000 & &2B 11 10390 22 14 109991?22 lEIHlia 18 i凶iaSHB G 14 1$ 10099 95 199

15、09 10093 ? 1060020"年12月M日判断是否生成最小生成树20111229 H求最小生成树4題出请输入所选功能直-4能构成最小生成树遍历所有城市最小生成树求最小生成树生成 尘 怠卜最 <一 骯 的成生 11-L r"市否有 入断历岀 输判询退请输入所选功能1 & 8 57 5 6 1 1 If 为为为为需 值值生E LD n 2 m 最-2 - - - TJ 2 2 2 14曰寸 * E - fl 为为为为为耐 一二二 L 二一二匸二一-L J:3HM退出求最小生成樹信一成 间构市 之雳 、帀否任 檸篇出H 12 3 4-请输入所选功能1-4re

16、&s Any key to cont inu.e程序源代码#in elude <stdio.h>#in elude <stri ng.h>#in elude <stdlib.h>#define max 20#define MAX_LNT 10typedef struct node /* 构造一个结构体，两个城市可以看成起点和终点，之间的道路可以看成 一个边 */int str; /* 起点 */int end; /* 终点 */int dis;/* 距离 */node;node pmax,temp; /*p 记录城市信息 */int pre100,r

17、ank100;/* 用于判断是否构成回路 */int n=0,arcsMAX_LNTMAX_LNT;/*n 表示城市个数， arcs 记录城市间权值 */int menu( ) /* 菜单函数 */int m;printf("2011 年 12 月 29 日nn");printf(" 求最小生成树 n");printf(" nn");printf("1 输入城市之间的信息 n");printf("2 判断是否能构成一个最小生成树 n");printf("3 遍历所有城市生成最小生成树

18、n");printf("4 退出 n");printf(" nn");printf(" 请输入所选功能 1-4n");system("color A");/* 改变界面颜色的，对程序没什么影响 */ scanf("%d",&m);return m;/* 下面三个函数作用是检验当一条边添加进去，是否会产生回路*/void set(int x)/* 初始化 */prex = x;rankx = 0;int find(int x)/* 找到这个点的祖先 */if(x != prex)

19、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 <= n;i +)/* 初始化数组 prex,rankx*/set(i

20、);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+) if(pj.dis <pindex.dis) index=j; temp=pindex;pindex=pi; pi=temp;for(i = 1;i <= k;i +)则执 if(find(pi.str) !

21、= 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); void create( ) /* 输入城市信息 */int i,j;printf(" 请输入

22、城市的个数 :n");scanf("%d",&n);printf(" 输入 %d 个城市的邻接矩阵 :n",n);for(i = 1;i <= n;i +)for(j = 1;j <= n;j +) scanf("%d",&arcsij);void display( ) /* 显示生成的最小生成树 */ if(n = 0)printf(" 这里没有城市之间的信息 n");return;printf(" 遍历所有城市得到最小生成树为： nnn");Kruskal( ); void judge( )/*