kruskal算法说明及图解.doc

无向网图及边集数组存储示意图V1V4V0V5V2V3V0V1V2V3V4V5vertex[6]=下标012345678from120234030to435555142weight121719252526343846Kruskal方法构造最小生成树的过程V1V0V4V5V3V2(a)一个图(b)最小生成树过程1(c)最小生成树过程2(d)最小生成树过程3(e)最小生成树过程4(c)最小生成树过程5伪代码1)初始化辅助数组parent[vertexNum];num=0;2)依次考查每一条边for(i=0;i<um;i++)vex1=edge[i].form所在生成树的根结点vex2=edge[i].to所在生成树的根结点If(vex1!=vex2)parent[vex2]=vex1;num++;if(num==vertexNum-1)算法结束构造过程中参数变化顶点集数组parentV0V1V2V3V4V5被考查边输出说明初始化parent-1-1-1-1-1-16棵生成树,均只有根结点parent-1-1-1-11-1(v1,v4)12(v1,v4)12vex1=1,vex2=4;parent[4]=1;parent-1-1-121-1(v2,v3)17(v2,v3)17vex1=2,vex2=3;parent[3]=2;parent-1-1-1210(v0,v5)19(v0,v5)19vex1=0,vex2=5;parent[5]=0;parent2-1-1210(v2,v5)25(v2,v5)25vex1=2,vex2=0;parent[0]=2;parent2-1-1210(v3,v5)25vex1=2,vex2=2;所在根结点相同parent2-11210(v4,v6)26(v4,v6)26vex1=1,vex2=2;parent[2]=1;parent2-11210生成树根结点是v1主要代码/**********构造函数************/template<classDataType>EdgeGraph<DataType>::EdgeGraph(DataTypea[],intn,inte){ vertexNum=n; edgeNum=e; inti,j,weight; for(intk=0;k<vertexNum;k++) vertex[k]=a[k]; for(k=0;k<edgeNum;k++) { cout<<"输入边依附的两个顶点的编号:"; cin>>i>>j; edge[k].from=i; edge[k].to=j; cout<<"请输入权重:"; cin>>weight; edge[k].weight=weight; }}/**********Kruskal算法构造最小生成树************/template<classDataType>voidEdgeGraph<DataType>::Kruskal(){intnum; intparent[MaxVertex],vex1,vex2; for(inti=0;i<vertexNum;i++) parent[i]=-1; for(i=0,num=0;i<edgeNum;i++) { vex1=FindRoot(parent,edge[i].from); vex2=Fin