Kruskal算法说明及图解.doc

《Kruskal算法说明及图解.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.无向网图及边集数组存储示意图V1V4V0V5V2V3V0V1V2V3V4V5vertex[6]=下标012345678from120234030to435555142weight1217192525263438462.Kruskal方法构造最小生成树的过程V1V0V4V5V3V2(a)一个图(b)最小生成树过程1(c)最小生成树过程2（d)最小生成树过程3(e)最小生成树过程4(c)最小生成树过程51.伪代码1）初始化辅助数组parent[vertexNum];num=0;2)依次考查每一条边for(i=0;i

2、树的根结点vex2=edge[i].to所在生成树的根结点If(vex1!=vex2)parent[vex2]=vex1;num++;if(num==vertexNum-1)算法结束2.构造过程中参数变化顶点集数组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

3、-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生成树根结点是v11.主要代码/**********构造函数************/templateEd

4、geGraph::EdgeGraph(DataTypea[],intn,inte){vertexNum=n;edgeNum=e;inti,j,weight;for(intk=0;k>i>>j;edge[k].from=i;edge[k].to=j;cout<<"请输入权重：";cin>>weight;edge[k].weight=weight;}}/**********Kruskal算法构造最小生成树*

5、***********/templatevoidEdgeGraph::Kruskal(){intnum;intparent[MaxVertex],vex1,vex2;for(inti=0;i"<

6、ge[i].to<<")"<<"weight:"<intEdgeGraph::FindRoot(intparent[],intv){intt=v;while(parent[t]>-1)t=parent[t];returnt;}/**********遍历输出************/template

7、DataType>voidEdgeGraph::Print(){for(inti=0;i