Kruskal算法说明及图解

《Kruskal算法说明及图解》由会员分享，可在线阅读，更多相关《Kruskal算法说明及图解（5页珍藏版）》请在装配图网上搜索。

1、1.无向网图及边集数组存储示意图vertex6=V0V1V2V3V4V5下标012345678from120234030to435555142weight1217192525263438462.Kruskal方法构造最小生成树的过程(a)一个图(b)最小生成树过程1最小生成树过程2(d)最小生成树过程3(e)最小生成树过程4(c)最小生成树过程53.伪代码1)初始化辅助数组parentvertexNum;num=0;2)依次考查每一条边 for(i=0; iarcNum; i+ ) vex1=edgei.form 所在生成树的根结点 vex2=edgei.to所在生成树的根结点 If(vex1

2、!=vex2)parentvex2=vex1;num+;if(num=vertexNum-1) 算法结束4.构造过程中参数变化、顶点集 数组、parentV0V1V2V3V4V5被考查边输出说明初始化parent-1-1-1-1-1-16棵生成树，均只后根结点parent-1-1-1-11-1(v1,v4)12(v1,v4)12vex1=1,vex2=4;parent4=1;parent-1-1-121-1(v2,v3)17(v2,v3)17vex1=2,vex2=3;parent3=2;parent-1-1-1210(v0,v5)19(v0,v5)19vex1=0,vex2=5;parent

3、5=0;parent2-1-1210(v2,v5)25(v2,v5)25vex1=2,vex2=0;parent0=2;parent2-1-1210(v3,v5)25vex1=2,vex2=2;所在根结点相同parent2-11210(v4,v6)26(v4,v6)26vex1=1,vex2=2;parent2=1;parent2-11210生成树根结点是v15.主要代码/*构造函数 */templateEdgeGraph:EdgeGraph(DataType a, int n, int e) vertexNum=n; edgeNum=e;int i,j,weight;for (int k=0

4、; kvertexNum; k+)vertexk=ak;for (k=0; kedgeNum; k+)coutij;edgek.from=i;edgek.to=j;coutweight;edgek.weight=weight;*Kruskal算法构造最小生成树 */template void EdgeGraph:Kruskal() int num;int parentMaxVertex, vex1, vex2;for (int i=0; ivertexNum; i+) parenti=-1;for (i=0,num=0; iedgeNum; i+)vex1=FindRoot(parent, e

5、dgei.from);vex2=FindRoot(parent, edgei.to);if (vex1!=vex2)cout ( edgei.from edgei.to ) weight:edgei.weight endl;parentvex2=vex1;num+;if (num=vertexNum-1) return;/*寻找根节点 */template int EdgeGraph:FindRoot(int parent, int v) int t=v;while(parentt -1)t=parentt;return t;/*遍历输出 */template void EdgeGraph:Print()for (int i=0; iedgeNum; i+)cout(edgei.fromedgei.to)weight:edgei.weightendl;6.结果截图发现不按大小输入 weight 的值则不能正确生成最小生成树如排好序输入时则得到正确的最小生成树结果正确，所以需要按大小顺序输入权值大小的 Kruskal 算法实际上对较复杂无向网图来说不适用。故思考在程序中添加一个对权值排序的函数（修改对应的 from,to）