最小生成树问题..docx

5.6题 最小生成树问题实习报告题目:最小生成树问题班级: 姓名: 学号: 完成日期:2015.1.7需求分析【问题描述】?若要在n个城市之间建役通信网络，只福要架设n-1条级路即可．如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。【基本要求】?（1）利用克鲁斯卡尔算法求图的最小生成树。 （2）能实现教科书6.5节中定义的抽象数据类型MFSet.以此表示构造生成树过程中的连通分量。 (3 ) 以文本形式输出生成树中各条边以及他们的权值．【测试数据】?书中7.4.3中用于演示Kruskal算法和Prim算法的无向图 概要设计1.1.抽象数据类型图的定义如下：ADT Graph{ 数据对象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（）失败，则操作失败。}ADT Graph1.2抽象数据类型MFSet的定义ADT MFSet { 数据对象：若设S是MFSet型的集合，则它由n(n0)个子集Si（i = 1,2...,n）构成，每个子集的成员代表在这个子集中的城市。 数据关系：S1 U S2 U S3 U... U Sn = S, Si包含于S（i = 1,2,...n） 基本操作：Init (n): 初始化集合，构造n个集合，每个集合都是单成员，根是其本身。rank数组初始化0 Find(x):查找x所在集合的代表元素。即查找根，确定x所在的集合，并路径压缩。 Merge(x, y):检查x与y是否在同一个集合，如果在同一个集合则返回假，否则按秩合并这两个集合并返回真。 }ADT MFSet; 2.本程序共包括三个模块主程序模块int main( ){定义图G；CreateGraph；执行kruskal算法；退出；}图模块——实现图抽象数据类型核心算法模块——实现kruskal算法void kruskal(MGraph G){int set[MAX_VERTEX_NUM],i,j;int k=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