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

数据构造课程设计说明书学院：信息科学与工程学院班级：计算机11-2完成人：姓名：学号：01050220姓名：学号：01050221指导教师：山东科技大学12课程设计任务书一、课程设计题目：构造能够使n个都市连接的最小生成树二、课程设计应解决的重要问题：（1）邻接矩阵的构造及其存储（2）判断与否能够生成最小生成树（3）克鲁斯算法的设计（4）运用克鲁斯算法构造最小生成树时与否产生回路的判断（5）界面的设计三、任务发出日期：-11-28课程设计完毕日期：-12

小组分工阐明小组编号35题目：构造可使n个都市连接的最小生成树小组分工状况：王露：算法设计，voidKruskal()函数，voidset()函数，voidfind()函数，voidUnion()函数王炜程：voidcreat()函数，voidjudge()函数，intmain()函数；intmenu()函数，voiddisplay()函数 组长签字：年月日指导教师对课程设计的评价成绩：指导教师签字：年月日

目录重要问题------------------------------------------------------------------5基本规定------------------------------------------------------------------5算法基本思想描述------------------------------------------------------5具体设计------------------------------------------------------------------51、数据构造的设计-----------------------------------------5<1>存储构造-------------------------------------------------------5<2>图的表达--------------------------------------------------------62、算法的设计---------------------------------------------6<1>克鲁斯卡尔算法设计----------------------------------------------6<2>避免不能构成最小生成树的图--------------------------------------6<3>模块构造及功效--------------------------------------------------7<4>重要模块算法描述------------------------------------------------7五、源程序清单-----------------------------------------------------------------9六、测试数据及测试成果-----------------------------------------------------91、开始画面---------------------------------------------------------92、输入信息---------------------------------------------------------103、数据解决---------------------------------------------------------10（1）判断能否构成最小生成树---------------------------------------10（2）遍历全部的最小生成树-----------------------------------------10（3）退出---------------------------------------------------------11七、课程设计总结--------------------------------------------------------------11八、附录--------------------------------------------------------------------------------11参考书目--------------------------------------------------------------------------15构造能够使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之间无边时对于网络，有当顶点i与顶点j之间有边时，且边上的权值为时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>模块构造及功效主程序主程序输入都市信息退出初始化判断与否为连通图求最小生成树判断与否构成回路将能够最小生成树的边集合打印输出最小生成树及代价打印输出最小生成树及代价intmain() //主程序intmenu() //菜单函数voidcreate() //输入都市信息函数voidjudge() //判断与否能够生成最小生成树函数voiddisplay()//打印输出voidset()//初始化pre[],rank[]函数voidfind（）//判断与否构成回路函数voidUnion()//将能构成最小生成树的边添加到一种集合voidKrushal()//克鲁斯算法求最小生成树<4>重要模块算法描述Krushal算法描述：/*下面三个函数作用是检查当一条边添加进去，与否会产生回路*/voidset(intx)/*初始化*/{ pre[x]=x; rank[x]=0;}intfind(intx)/*找到这个点的祖先*/{ 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].dis<p[index].dis)index=j; temp=p[index]; p[index]=p[i]; p[i]=temp; } for(i=1;i<=k;i++) { 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); }五、源程序清单（详见附录）六、测试数据及测试成果11以一种6个都市、10条边的网络图为例进行测试11 161120 11 51119 611221491118网络图GE=邻接矩阵1、开始画面2、输入信息设立两顶点之间无边时∞权值为10000003、数据解决(1)、判断能否构成最小生成树（2）、遍历全部都市生成最小生成数21 16 2163 11 563 654 1854生成的最小生成树（3）、退出七、课程设计总结通过最小生成树的学习，我学会了树的多个存储构造和遍历办法，最小生成树的设计能够应用于我们生活中。我们能够把生活中碰到的实际问题转化为一种算法问题来进行解决。八、附录源程序：#include<stdio.h>#include<string.h>#include<stdlib.h>typedefstructnode/*构造一种构造体，两个都市能够当作起点和终点，之间的道路能够当作一种边*/{ intst;/*起点*/ inted;/*终点*/ intdis;/*距离*/}node;nodep[1000],temp; /*p统计都市信息*/intpre[1000],rank[1000];/*用于判断与否构成回路*/intn=0,a[100][100];/*n表达都市个数，a[][]统计都市间权值*/intmenu()/*菜单函数*/{ intm; printf("求最小生成树\n"); printf("________________________________\n\n"); printf("1输入都市之间的信息\n"); printf("2判断与否能构成一种最小生成树\n"); printf("3遍历全部都市生成最小生成树\n"); printf("4退出\n"); printf("________________________________\n\n"); printf("请输入所选功效--4\n"); scanf("%d",&m); returnm;}/*下面三个函数作用是检查当一条边添加进去，与否会产生回路*/voidset(intx)/*初始化*/{ pre[x]=x;}intfind(intx)/*找到这个点的祖先*/{ if(x!=pre[x])pre[x]=find(pre[x]); returnpre[x];}voidUnion(intx,inty)/*将这两个添加到一种集合里去*/{ x=find(x); y=find(y);pre[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].dis<p[index].dis)index=j; temp=p[index]; p[index]=p[i]; p[i]=temp; } for(i=1;i<=k;i++) { 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); }voidcreate() /*输入都市信息*/ { inti,j; if(n!=0) { charstr[100]; printf("与否要拟定输入新的都市之间的信息?(y/n)?\n"); scanf("%s",str); if(strcmp(str,"n")==0) return; } printf("请输入都市的个数:\n"); scanf("%d",&n); printf("输入%d个都市的邻接矩阵:\n",n); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) scanf("%d",&a[i][j]); } }voiddisplay() /*显示生成的最小生成树*/ { if(n==0) { printf("这里没有都市之间的信息\n"); return; } printf("遍历全部都市得到最小生成树为：\n\n\n"); Kruskal(); }voidjudge()/*判断与否能够生成最小生成树*/ { intclose[100],low[100],i,j,ans=0;/*close[j]表达离j近来的顶点，low[j]表达离j最短的距离*/ intuse[100]; use[1]=1; for(i=2;i<=n;i++) {low[i]=a[1][i];/*初始化*/close[i]=1;use[i]=0;