最小生成树的课程设计.doc

数据结构与算法课程设计报告 课程设计题目： 构造可以使n个城市连接的最小生成树专业班级： 信息与计算科学1001班 姓 名： 学 号： 设计室号： 理学院机房 设计时间： 2011-12-26 批阅时间： 指导教师： 成 绩： 构造可以使n个城市连接的最小生成树主要任务：给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。设计该程序的基本要求：1、城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。2、表示城市间距离网的邻接矩阵（要求至少6个城市，10条边）3、最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。总体设计 1 该程序的主要功能：能实现根据输入城市的信息可以判断该城市间的距离网是否构成最小生成树，遍历城市生成最小生成树，通过计算得到最小生成树的代价。 2 该城市间的距离网用邻接矩阵表示 3 用克鲁斯卡尔（Kruskal）算法建立最小生成树详细设计说明 1 该程序的主要功能：能实现根据输入城市的信息可以判断出该城市间的距离网是否构成最小生成树，遍历城市生成最小生成树，通过计算得到最小生成树的代价。 该程序的模块结构功能图及主要函数如下： 开始 输入城市信息是否为连通图？ 求最小生成树初始化是否构成回路？将最小生成树边集合打印出最小生成树的权值与最小生成树的代价退出a) int main ( ) /主程序b) int menu ( ) /菜单函数c) void create ( ) /输入城市信息函数d) void judge ( ) /判断是否能够生成最小生成树函数e) void display( ) /打印输出f) void set ( ) /初始化pre,rank函数g) void find ( ) /判断是否构成回路函数h) void Union ( ) /将能构成最小生成树的边添加到一个集合l） void Krushal( ) /克鲁斯算法求最小生成树体会确定程序功能设计出总体流程对整个设计进行非常重要，明确要完成设计需要的程序算法，为整个设计流程划出大纲，可以使整个设计思路更加简单明了。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表示城市个数，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; 该城市间的距离网使用邻接矩阵表示，邻接矩阵存储方法（数组存储方法），利用两个数组来存储一个图。用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=（V，E），则令最小生成树的初始状态为只有n 顶点而无边的非连通图T=(V, )，图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。以此类推，直至T中所有顶点都在同一个连通分量上为止。（2）克鲁斯卡尔算法设计a. 设置计数器E，初值为0，记录已选中的边数。将所有边从小到大排序，存于p 中。b. 从p 中选择一条权值最小的边，检查其加入到最小生成树中是否会构成回路，若是，则此边不加入生成树；否则，加入到生成树中，计数器E累加1。 c. 从E中删除此最小边，转b继续执行，直到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(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.dis);/*将这条边的起点、终点打印出来*/ans += pi.dis;/*说明这条路段要用*/Union(pi.str,pi.end); printf(t遍历所有城市得到最小生成树的代价为: %dnn,ans);设置集合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 = 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);克鲁斯卡尔算法(Kruskals algorithm)是两个经典的最小生成树算法的较为简单理解的一个。这里面充分体现了贪心算法的精髓。 克鲁斯卡尔算法生成最小生成树的过程 （3）防止不能构成最小生成树的图为避免输入的图构成的不是连通图，设计了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; 调试与测试211以一个6个城市、10条边的网络图为例进行测试 1663 20115196 45 22 14 9 18网络图GE = 邻接矩阵生成界面输入城市间信息判断是否生成最小生成树遍历所有城市最小生成树退出程序源代码#include #include #include #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表示城市个数，arcs记录城市间权值*/int menu( ) /*菜单函数*/ int m;printf(.2011年12月29日.nn);printf( 求最小生成树n);printf( _nn);printf( 1 输入城市之间的信息n);printf( 2 判断是否能构成一个最小生成树n);printf( 3 遍历所有城市生成最小生成树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) 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);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) != 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(请输入城市的个数: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( )/*判断