Kruskal算法说明及图解.doc

1. 无向网图及边集数组存储示意图V1V4V0V5V2V3V0V1V2V3V4V5 vertex6= 下标 0 1 2 3 4 5 6 7 8from 1 2 0 2 3 4 0 3 0to 4 3 5 5 5 5 1 4 2weight 12 17 19 25 25 26 34 38 46 2. Kruskal方法构造最小生成树的过程V1 V0V4V5V3V2 (a)一个图 (b)最小生成树过程1 (c)最小生成树过程2 （d)最小生成树过程3 (e)最小生成树过程4 (c)最小生成树过程5 3. 伪代码1）初始化辅助数组parentvertexNum;num=0;2) 依次考查每一条边for(i=0; iarcNum; i+ ) vex1=edgei.form所在生成树的根结点 vex2=edgei.to所在生成树的根结点 If(vex1!=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;parent5=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; 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, edgei.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.from edgei.to)weight:edgei.weightendl;6. 结果截图 发现不按大小输入weight的值则不能正确生成最小生成树 如排好序输入时则得