两种算法实现最小生成树

《两种算法实现最小生成树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构上机实验报告题目：两种算法实现最小生成树学生姓名学生学号学院名称计算机学院专业计算机科学与技术时间2014.12.9目录第一章需求分析11.1原题表述11.2问题解决方案1第二章概要设计22.1抽象数据类型22.2主要算法描述22.1.1Prim算法实现22.1.2Kruskal算法实现32.3主要算法分析3第三章概要设计43.1程序代码43.1.1Prim算法实现43.1.2Kruskal算法实现6第四章调试分析94.1出现的问题及解决方法9第五章测试分析105.1测试样例10I第一章需求分析1.1原题表述某市为实现交通畅行，

2、计划使全市中的任何两个村庄之间都实现公路互通，虽然不需要直接的公路相连，只要能够间接可达即可。现在给出了任意两个城镇之间修建公路的费用列表，以及此两个城镇之间的道路是否修通的状态，要求编写程序求出任意两村庄都实现公路互通的最小成本。输入参数：测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N(1

3、的一行，输出实现后所需的最小成本值1.2问题解决方案第一种方案：使用Prim算法首先以一个结点作为最小生成树的初始结点，然后以迭代的方式找出与最小生成树中各结点权重最小边，并加入到最小生成树中。加入之后如果产生回路则跳过这条边，选择下一个结点。当所有结点都加入到最小生成树中之后，就找出了连通图中的最小生成树了。第二种方案：使用kruskal算法算法过程：1.将图各边按照权值进行排序2.将图遍历一次，找出权值最小的边，（条件：此次找出的边不能和已加入最小生成树集合的边构成环），若符合条件，则加入最小生成树的集合中。不符合条件则继续遍历图，

4、寻找下一个最小权值的边。3.递归重复步骤1，直到找出n-1条边为止（设图有n个结点，则最小生成树的边数应为n-1条），算法结束。得到的就是此图的最小生成树。10第二章概要设计2.1抽象数据类型ADTGraph{数据对象V：V是具有相同特性的数据元素的和，称为顶点级。数据关系R：R={VR}VR={

5、v,wV且P（v,w），表示从v到w的弧，谓词P（v,w）定义了弧的意义或信息}基本操作：CreatGraph（&G,V）初始条件：v是顶点数量操作结果：构造含有V个顶点的图GPrim(G)初始条件：图G存在操作

6、结果：找到图G中最小生成树Kruskal（G）初始条件：图G存在操作结果：找到图G中最小生成树}ADTGraph2.2主要算法描述2.1.1Prim算法实现102.2.2Kruskal算法实现2.3主要算法分析Prim算法时间复杂度为O（n2），与图中顶点个数有关，而与边数无关。Kruskal算法时间复杂度为O（eloge），与途中的边数有关，而与顶点数无关。10第三章详细设计3.1程序代码3.1.1Prim算法实现#include#defineNUM200//最大顶点数#defineMAX40000//最大值//定义

7、邻接矩阵的结构typedefstruct{intedges[NUM][NUM];//邻接矩阵intn;//顶点数inte;//边数}MGraph;//构造邻接矩阵，v表示顶点数voidCreatGraph(MGraph&G,intv){G.n=v;G.e=v*(v-1)/2;for(inti=1;i<=G.n;i++){//初始化邻接矩阵for(intj=1;j<=G.n;j++){G.edges[i][j]=MAX;}}for(inti=1;i<=G.e;i++){//构造邻接矩阵//v1,v2一条路连接的两村庄，cost修路费用，b

8、uild修建状态intv1,v2,cost,build;scanf("%d%d%d%d",&v1,&v2,&cost,&build);if(build==1)cost=0;G.edges[v1][v2]=cost;G.edges[v2][v1]=cost;}}intPrim(MGraphG){intresult=0;//用于记录修路成本intlowcost[NUM];10//存放生成树顶点集合内顶点到生成树外各顶点的各边上的当前最小权值intvex[NUM];//记录生成树顶点集合外各顶点距离集合内哪个顶点最近(即权值最小)for(in

9、ti=1;i<=G.n;i++){//初始化lowcost[],vex[]lowcost[i]=G.edges[1][i];vex[i]=1;}vex[1]=-1;//加到生成树顶点集合for(inti=2