构造可以使n个城市连接最小生成树

-1-数据结构课程设计说明书学院：信息科学与工程学院班级：计算机11-2完成人：姓名：学号：201101050220姓名：学号：201101050221指导教师：山东科技大学2012年12月13日-2-课程设计任务书一、课程设计题目：构造可以使n个城市连接的最小生成树二、课程设计应解决的主要问题：（1）邻接矩阵的构造及其存储（2）判断是否能够生成最小生成树（3）克鲁斯算法的设计（4）利用克鲁斯算法构造最小生成树时是否产生回路的判断（5）界面的设计三、任务发出日期：2012-11-28课程设计完成日期：2012-12-13-3-小组分工说明小组编号35题目：构造可使n个城市连接的最小生成树小组分工情况：王露：算法设计，voidKruskal()函数，voidset()函数，voidfind()函数，voidUnion()函数王炜程：voidcreat()函数，voidjudge()函数，intmain()函数；intmenu()函数，voiddisplay()函数组长签字：年月日指导教师对课程设计的评价成绩：指导教师签字：年月日-4-目录一、主要问题------------------------------------------------------------------5二、基本要求------------------------------------------------------------------5三、算法基本思想描述------------------------------------------------------5四、详细设计------------------------------------------------------------------51、数据结构的设计-----------------------------------------51存储结构-------------------------------------------------------52图的表示--------------------------------------------------------62、算法的设计---------------------------------------------61克鲁斯卡尔算法设计----------------------------------------------62防止不能构成最小生成树的图--------------------------------------63模块结构及功能--------------------------------------------------74主要模块算法描述------------------------------------------------7五、源程序清单-----------------------------------------------------------------9六、测试数据及测试结果-----------------------------------------------------91、开始画面---------------------------------------------------------92、输入信息---------------------------------------------------------103、数据处理---------------------------------------------------------10（1）判断能否构成最小生成树---------------------------------------10（2）遍历所有的最小生成树-----------------------------------------10（3）退出---------------------------------------------------------11七、课程设计总结--------------------------------------------------------------11八、附录--------------------------------------------------------------------------------11参考书目--------------------------------------------------------------------------15-5-构造可以使n个城市连接的最小生成树一、主要问题给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。二、基本要求（1）城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。（2）表示城市间距离网的邻接矩阵（要求至少6个城市，10条边）（3）最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。三、算法基本思想描述Kruskal算法思想基本描述：假设连通图N=（V，{E}），则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V,{})，图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。以此类推，直至T中所有顶点都在同一个连通分量上为止。四、详细设计1、数据结构的设计1存储结构邻接矩阵存储方法（数组存储方法），利用两个数组来存储一个图，其构造原理比较简单。对于具有n个顶点的图G=(V,E),定义一个具有n个元素的一维数组VERTEX[0..n-1]，将图中顶点的数据信息分别存入该数组的一个数组元素中。另外，定义一个二维数组A[0..n-1][0..n-1],该二维数组通常被称为邻接矩阵。若以顶点在VERTEX数组中的下标来代表一个顶点，则邻接矩阵中元素A[i][j]存放顶点i到顶点j之间的关系信息，有1当顶点i与顶点j之间有边时A[i][j]=0当顶点i与顶点j之间无边时对于网络，有-6-ijW当顶点i与顶点j之间有边时，且边上的权值为ijW时A[i][j]=当顶点i与顶点j之间无边时2图的表示用n表示城市的个数，st表示起始城市，ed表示终点城市，dis表示两城市间的距离。下面是构成该结构体的源代码：typedefstructnode{intst;/*起点*/inted;/*终点*/intdis;/*距离*/}node;nodep[]；/*p[]数组用来储存城市和城市间的信息*/2、算法的设计1克鲁斯卡尔算法设计a.设置计数器E，初值为0，记录已选中的边数。将所有边从小到大排序，存于p[]中。b.从p[]中选择一条权值最小的边，检查其加入到最小生成树中是否会构成回路，若是，则此边不加入生成树；否则，加入到生成树中，计数器E累加1。c.从E中删除此最小边，转b继续执行，直到k=n-1,算法结束d.判断是否构成回路的方法：设置集合S，其中存放已加入到生成树中的边所连接的顶点集合，当一条新的边要加入到生成树中时，检查此边所连接的两个顶点是否都已经在S中，若是，则表示构成回路，否则，若有一个顶点不在S中或者两个顶点都不在S中，则不够成回路。2防止不能构成最小生成树的图为避免输入的图构成的不是连通图，设计了judge()函数来判断输入数据构成的是否为连通图，此函数的主要算法是源于普里姆算法，经过改编，形成了新的函数。3模块结构及功能-7-a)intmain()//主程序b)intmenu()//菜单函数c)voidcreate()//输入城市信息函数d)voidjudge()//判断是否能够生成最小生成树函数e)voiddisplay()//打印输出f)voidset()//初始化pre[],rank[]函数g)voidfind（）//判断是否构成回路函数h)voidUnion()//将能构成最小生成树的边添加到一个集合i)voidKrushal()//克鲁斯算法求最小生成树4主要模块算法描述Krushal算法描述：/*下面三个函数作用是检验当一条边添加进去，是否会产生回路*/voidset(intx)/*初始化*/{pre[x]=x;rank[x]=0;}intfind(intx)/*找到这个点的祖先*/主程序输入城市信息退出初始化判断是否为连通图求最小生成树判断是否构成回路将能够最小生成树的边集合打印输出最小生成树及代价-8-{if(x!=pre[x])pre[x]=find(pre[x]);returnpre[x];}voidUnion(intx,inty)/*将这两个添加到一个集合里去*/{x=find(x);y=find(y);if(rank[x]=rank[y]){pre[y]=x;rank[x]++;}elsepre[y]=x;}voidKruskal(){intans=0,i,j,k=0;/*ans用来记录生成最小树的权总值*/intindex;intcount=0;/*记录打印边的条数*/for(i=1;i=n;i++)/*初始化数组pre[x],rank[x]*/set(i);for(i=1;i=n;i++){for(j=i+1;j=n;j++){p[++k].st=i;p[k].ed=j;p[k].dis=a[i][j];/*先把所有城市之间的路段看成一个边*/}}for(i=1;i=k;i++)/*把所有的边按从小到大进行排序*/{index=i;for(j=i+1;j=k;j++)if(p[j].disp[index].dis)index=j;temp=p[index];p[index]=p[i];p[i]=temp;}for(i=1;i=k;i++){-9-if(find(p[i].st)!=find(p[i].ed))/*如果这两点连接在一起不构成一个回路，则执行下面操作*/{printf(\t第%d条路段为：%d--%d,权值为%d\n,++count,p[i].st,p[i].ed,p[i].dis);/*将这条边的起点、终点打印出来*/ans+=p[i].dis;/*说明这条路段要用*/Union(p[i].st,p[i].ed);}}printf(\t遍历所有城市得到最小生成树的代价为:%d\n\n,ans);}五、源程序清单（详见附录）六、测试数据及测试结果以一个6个城市、10条边的网络图为例进行测试16201151962214918网络图GE=9591814618221914221120561116192016邻接矩阵1、开始画面111111-10-2、输入信息设置两顶点之间无边时∞权值为10000003、数据处理(1)、判断能否构成最小生成树（2）、遍历所有城市生成最小生成数16115618生成的最小生成树153264-11-（3）、退出七、课程设计总结通过最小生成树的学习，我学会了树的多种存储结构和遍历方法，最小生成树的设计可以应用于我们生活中。我们可以把生活中遇到的实际问题转化为一种算法问题来进行解决。八、附录源程序：#includestdio.h#includestring.h#includestdlib.htypedefstructnode/*构造一个结构体，两个城市可以看成起点和终点，之间的道路可以看成一个边*/{intst;/*起点*/inted;/*终点*/intdis;/*距离*/}node;nodep[1000],temp;/*p记录城市信息*/intpre