广工数据结构课程设计最小生成树

课程设计课程名称数据结构学院专业班级学号学生姓名指导教师2015年7月2日1.需求分析题目：最小生成树问题若要在n个城市之间建设通讯网络，只需要架设n-1条线路即可。如何以最低的经济代价建设这个通讯网，是一个网的最小生成树问题。要求：（1）利用克鲁斯卡尔算法求网的最小生成树。（2）实现并查集。以此表示构造生成树过程中的连通分量。（3）以文本形式输出生成树中各条边以及他们的权值。输入的形式和输入值的范围：十进制数，0—100。输出的形式：十进制数。程序所能达到的功能：遍历所有城市生成最小生成树。测试数据：正确数据：城市个数3；3个城市的邻接矩阵：(1,2,3;2,100,4;3,4,6)输出结果：第1条路段为1——2，权值为2第2条路段为1——3，权值为3遍历所有城市得到最小生成树的代价为：5错误数据：城市个数3；城市的邻接矩阵：(-2,5,1;3,0,1;3,2,1)输出结果：输入错误，请重新输入2.概要设计数据类型定义如下：typedefstructnode{intstr;/*起点*/intend;/*终点*/intdis;/*距离*/}node;nodep[max],temp;/*p记录城市信息*/intpre[100],rank[100];/*用于判断是否构成回路*/intn=0,arcs[MAX_LNT][MAX_LNT];/*n表示城市个数，arcs[][]记录城市间权值*/主程序流程如下：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,算法结束。判断是否回路：设置集合S，其中存放已加入到生成树中的边所连接的顶点集合，当一条新的边要加入到生成树中时，检查此边所连接的两个顶点是否都已经在S中，若是，则表示构成回路，否则，若有一个顶点不在S中或者两个顶点都不在S中，则不够成回路。/*需要的函数声明*/intmain()//主程序intmenu()//菜单函数voidcreate()//输入城市信息函数voidjudge()//判断是否能够生成最小生成树函数voiddisplay()//打印输出voidset()//初始化pre[],rank[]函数voidfind()//判断是否构成回路函数voidUnion()//将能构成最小生成树的边添加到一个集合voidKrushal()//克鲁斯算法求最小生成树/*菜单函数*/intmenu(){intm;printf(..........................2015年7月2日......................\n\n);printf(求最小生成树\n);printf(________________________________\n\n);printf(1输入城市之间的信息\n);printf(2判断是否能构成一个最小生成树\n);printf(3遍历所有城市生成最小生成树\n);printf(0退出\n);printf(________________________________\n\n);printf(请输入所选功能0-3\n);scanf(%d,&m);if(m0||m3)return4;returnm;}/*下面三个函数作用是检验当一条边添加进去，是否会产生回路*/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].str=i;p[k].end=j;p[k].dis=arcs[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++){if(find(p[i].str)!=find(p[i].end))/*如果这两点连接在一起不构成一个回路，则执行下面操作*/{printf(\t第%d条路段为：%d--%d,权值为%d\n,++count,p[i].str,p[i].end,p[i].dis);/*将这条边的起点、终点打印出来*/ans+=p[i].dis;/*说明这条路段要用*/Union(p[i].str,p[i].end);}}printf(\t遍历所有城市得到最小生成树的代价为:%d\n\n,ans);}/*输入城市信息*/voidcreate(){inti,j;printf(请输入城市的个数（1—30）:\n);scanf(%d,&n);if(n=0||n30){printf(输入错误，请重新输入\n);return;}printf(输入%d个城市存储边(带权)的数组（数值范围：1-99，∞用100表示，）:\n,n);for(i=1;i=n;i++){for(j=1;j=n;j++){scanf(%d,&arcs[i][j]);if(arcs[i][j]1||arcs[i][j]100){printf(输入错误，请重新输入\n);return;}}}for(i=0;in;i++)for(j=0;ji;j++)if(arcs[i][j]!=arcs[j][i])/*判断矩阵是否对称*/{printf(输入错误，请重新输入\n);return;}}/*显示生成的最小生成树*/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]=arcs[1][i];/*初始化*/close[i]=1;use[i]=0;}for(i=1;in;i++){intmin=100000000,k=0;for(j=2;j=n;j++){if(use[j]==0&&minlow[j])/*找到最小的low[]值，并记录*/{min=low[j];k=j;}}for(j=2;j=n;j++){if(use[j]==0&&low[j]arcs[k][j]){low[j]=arcs[k][j];/*修改low[]值和close[]值*/close[j]=k;}}ans+=arcs[close[k]][k];}if(ans=100000000)printf(不能构成最小生成树\n);elseprintf(能构成最小生成树\n);}/*主函数*/voidmain(){while(1){switch(menu()){case1:create();break;/*输入城市信息*/case2:judge();break;/*判断是否能够生成最小生成树*/case3:display();break;/*显示生成的最小生成树*/case0:exit();default:printf(输入错误，请重新选择。\n);break;}}}4.调试分析本课程设计重点在于生成最小生成树算法。克鲁斯卡尔算法将图中边按其权值由小到大的次序顺序选取,若选边后不形成回路,则保留作为一条边,若形成回路则除去，依次选够(n-1)条边,即得最小生成树。在克鲁斯卡尔算法中，图的存贮结构采用边集数组,且权值相等的边在数组中排列次序可以是任意的，该方法对于边相对比较多的不是很实用。本课程设计为求最小生成树，先要构造一个结构体，再用邻接矩阵的形式表现出来。城市间的距离网使用邻接矩阵表示，邻接矩阵存储方法（数组存储方法），利用两个数组来存储一个图。用a[i][j]数组，利用邻接矩阵方式来储存城市与城市间信息。5.用户使用说明按顺序依次输入城市之间的信息，判断是否能构成一个最小生成树，再生成遍历所有城市的最小生成树。如果输入过程中出现错误，需重新输入。城市存储边(带权)矩阵中的∞用100表示，矩阵必须对称。6.测试结果7.源代码#includestdio.h#includestring.h#includestdlib.h#definemax100#defineMAX_LNT30typedefstructnode/*构造一个结构体，两个城市可以看成起点和终点，之间的道路可以看成一个边*/{intstr;/*起点*/intend;/*终点*/intdis;/*距离*/}node;nodep[max],temp;/*p记录城市信息*/intpre[100],rank[100];/*用于判断是否构成回路*/intn=0,arcs[MAX_LNT][MAX_LNT];/*n表示城市个数，arcs[][]记录城市间权值*/intmenu()/*菜单函数*/{intm;printf(..........................2015年7月2日......................\n\n);printf(求最小生成树\n);printf(________________________________\n\n);printf(1输入城市之间的信息\n);printf(2判断是否能构成一个最小生成树\n);printf(3遍历所有城市生成最小生成树\n);printf(0退出\n);printf(________________________________\n\n);printf(请输入所选功能0-3\n);scanf(%d,&m);if(m0||m3)return4;returnm;}/*下面三个函数作用是检验当一条边添加进去，是否会产生回路*/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]++;}elsep