最小生成树问题

5.6题最小生成树问题实习报告题目:最小生成树问题班级:姓名:学号:完成日期:2015.1.7一．需求分析【问题描述】若要在n个城市之间建役通信网络，只福要架设n-1条级路即可．如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。【基本要求】（1）利用克鲁斯卡尔算法求图的最小生成树。（2）能实现教科书6.5节中定义的抽象数据类型MFSet.以此表示构造生成树过程中的连通分量。(3)以文本形式输出生成树中各条边以及他们的权值．【测试数据】书中7.4.3中用于演示Kruskal算法和Prim算法的无向图二．概要设计1.1.抽象数据类型图的定义如下：ADTGraph{数据对象V：V是具有相同特性的数据元素的集合，成为顶点集。数据关系R：R={VR}VR={v,w|v，w∈V且P（v，w），v，w表示从v到w的弧，谓词P（v，w）定义了弧v，w的意义或信息}基本操作P：CreateGraph（&G）；初始条件：图不存在。操作结果：按输入提示构造图G。DestoryGraph（&G）；初始条件：图G存在。操作结果：销毁图G。LocateVex（G，u）；初始条件：图G存在，u和G中是顶点有相同特征。操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其他信息。GetVex（G，v）；初始条件：图G存在，v是G中某个顶点。操作结果：返回v的值。PutVex（&G，v，value）；初始条件：图G存在，v是G中某个顶点。操作结果：对V赋值valueFirstAdjVex（G，v）；初始条件：图G存在，v是G中某个顶点。操作结果：返回v的第一个邻接顶点。若顶点在G中没有顶点，则返回“空”。NextAdjVex（G，v，w）；初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。操作结果：返回v的（相对于w的）下一个邻接顶点。若w是v的最后一个邻接顶点，则返回“空”。InsertVex（&G，v）；初始条件：图G存在，v和途中顶点有相同特征。操作结果：在图G中添加新顶点v。DeleteVex（&G，v）；初始条件：图G存在，v是G中某个顶点。操作结果：删除G中顶点v及其相关的弧。InsertArc（&G，v，w）；初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中加弧v，w，若G是无向的，则增添对称弧v，w。DeleteArc（&G，v，w）；初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中删弧v，w，若G是无向的，则删除对称弧v，w。DFSTravrese（G，Visit（））；初始条件：图G存在，Visit是顶点的应用函数。操作结果：对图进行深度优先遍历。在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦Visit（）失败，则操作失败。BFSTravrese（G，Visit（））；初始条件：图G存在，Visit是顶点的应用函数。操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦Visit（）失败，则操作失败。}ADTGraph1.2抽象数据类型MFSet的定义ADTMFSet{数据对象：若设S是MFSet型的集合，则它由n(n0)个子集Si（i=1,2...,n）构成，每个子集的成员代表在这个子集中的城市。数据关系：S1US2US3U...USn=S,Si包含于S（i=1,2,...n）基本操作：Init(n):初始化集合，构造n个集合，每个集合都是单成员，根是其本身。rank数组初始化0Find(x):查找x所在集合的代表元素。即查找根，确定x所在的集合，并路径压缩。Merge(x,y):检查x与y是否在同一个集合，如果在同一个集合则返回假，否则按秩合并这两个集合并返回真。}ADTMFSet;2.本程序共包括三个模块1)主程序模块intmain(){定义图G；CreateGraph；执行kruskal算法；退出；}2）图模块——实现图抽象数据类型3）核心算法模块——实现kruskal算法voidkruskal(MGraphG){intset[MAX_VERTEX_NUM],i,j;intk=0,a=0,b=0,min=G.arcs[a][b];for(i=0;iG.vexnum;i++)set[i]=i;printf(最小代价生成树的各条边为:\n);while(kG.vexnum-1){for(i=0;iG.vexnum;++i)for(j=i+1;jG.vexnum;++j)if(G.arcs[i][j]min){min=G.arcs[i][j];a=i;b=j;}if(set[a]!=set[b]){printf(%s-%s,G.vexs[a],G.vexs[b]);printf(%d\n,G.arcs[a][b]);k++;for(i=0;iG.vexnum;i++)if(set[i]==set[b])set[i]=set[a];}min=G.arcs[a][b]=1000000;}三．详细设计#includestdio.h#includestdlib.h#includestring.h#defineMAX_NAME20#defineMAX_VERTEX_NUM50typedefcharVertex[MAX_NAME];/*顶点名字串*/TypedefintAdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct/*定义图*/{Vertexvexs[MAX_VERTEX_NUM];AdjMatrixarcs;intvexnum,arcnum;}MGraph;intLocateVex(MGraph*G,Vertexu){inti;for(i=0;iG-vexnum;++i)if(strcmp(G-vexs[i],u)==0)returni;return-1;}voidCreateGraph(MGraph*G){inti,j,k,w;Vertexva,vb;printf(请输入无向网G的顶点数和边数(以空格为分隔)\n);scanf(%d%d,&G-vexnum,&G-arcnum);printf(请输入%d个顶点的值:\n,G-vexnum);for(i=0;iG-vexnum;++i)/*构造顶点集*/scanf(%s,G-vexs[i]);for(i=0;iG-vexnum;++i)/*初始化邻接矩阵*/for(j=0;jG-vexnum;++j)G-arcs[i][j]=1000000;/*表示无穷大*/printf(请输入%d条边的顶点1顶点2权值(以空格为间隔):\n,G-arcnum);for(k=0;kG-arcnum;++k){scanf(%s%s%d,va,vb,&w);i=LocateVex(G,va);/*定位va为横着的第i个*/j=LocateVex(G,vb);/*定位vb为竖着着的第j个*/G-arcs[i][j]=G-arcs[j][i]=w;/*矩阵是对称的*/}}voidkruskal(MGraphG){intset[MAX_VERTEX_NUM],i,j;intk=0,a=0,b=0,min=G.arcs[a][b];for(i=0;iG.vexnum;i++)set[i]=i;printf(最小代价生成树的各条边为:\n);while(kG.vexnum-1){for(i=0;iG.vexnum;++i)for(j=i+1;jG.vexnum;++j)if(G.arcs[i][j]min){min=G.arcs[i][j];a=i;b=j;}if(set[a]!=set[b]){printf(%s-%s,G.vexs[a],G.vexs[b]);printf(%d\n,G.arcs[a][b]);k++;for(i=0;iG.vexnum;i++)if(set[i]==set[b])set[i]=set[a];}min=G.arcs[a][b]=1000000;}}intmain(){MGraphg;CreateGraph(&g);kruskal(g);return0;}四．演示程序的层次结构和流程图五．调试分析1.这个程序的kruskal算法理解起来不难，但是具体的代码实层次结构流程图现是比较复杂的，通过室友百度书籍了解大致的框架，最大的困难在防止环的生成上遇到比较大的麻烦，由于对辅助数组运用不习惯，在室友建议下选用了别的方法。2.由于我周五上课时间冲突，导致我代码的编写没有助教的帮忙就，但单独完成上机任务还是非常困难的，虽然我借助了百度谷歌等搜索引擎，还翻了一下关于算法的书，借鉴了一些思想，但是也不及助教老师的耳提面命，所以代码方面也存在不少问题。3.本题中主要算法kruskal的时间复杂度为O(G.vexnum^4)，空间复杂度为O(MAX_VERTEX_NUM)。4.总结一下这个实验比较难，花费了我不少时间，与前两次困难不同的是，这次实验在C语言语法上没有感到困难，而是在具体算法的实现上花费了很多心思，感觉自己应该多读书，更好理解编程思想，而不是像以前那样停留在语法层次上。六．用户手册1.本程序的运行环境为DOS操作系统，执行文件为最小生成树.exe2.进入延时程序后即现实文本方式的用户界面3.根据提示输入数据，间隔符为“空格”结束符为“回车符”七．测试结果按照测试图数据输入，得到运行结果