else return o void merge ec( VexInfo&vexs[, int ecl,ntec2y/合并连通分量ecl和cc2 for(i=0; vexs[i].vex; i++) f(vexs[].ecno-ec2) vexs[ieco==ec1; i//merge ec void Min Span Tree Kruscal(Graph G, Edge Set Type &Edge Set, CSTree &T)/kBj 最小生成树的克鲁斯卡尔算法 Init Vexlnfo(vexs, G. vexnum); enum=G丶 vexnum;/连通分量个数 while(ecnu>1) GetMinEdge(EdgeSet,u,v),选出最短边 if( is ec( vex. uv)伽和v属于不同连通分量 Addto STRee(,uv)∥加入到生成树中 merge ec(vexs, vexsu]ecno, vex[v].ecn),∥合并连通分量 ecnum-- DelMinedge( EdgeSet,u,v)∥从边集中删除 //while i/InsPan Tree Kruscal void addto_ CSTree(STRee& T, int i, int D把边(ij)添加到孩子兄弟链表表示的树 T中 p= Locate(Ii;∥找到结点i对应的指针p过程略 q(CS TNode*)malloc(sizeof(CS TNode)); q->data=j ifp→> firstchild)/双亲还没有孩子 p> firstchild=q,∥作为双亲的第一个孩子 else∥双亲已经有了孩子 for(rp->firstchild; r ->nextsib, r=r->nextsib) r-> nextsib=q;∥作为双亲最后一个孩子的兄弟 i//Addto STRee 分析本算法使用一维结构体变量数组来表示等价类每个连通分量所包含的所有 结点属于一个等价类在这个结构上实现了初始化,判断元素是否等价(两个结点 是否属于同一个连通分量)合并等价类连通分量)的操作else return 0; }//is_ec void merge_ec(VexInfo &vexs[ ],int ec1,int ec2)//合并连通分量 ec1 和 ec2 { for(i=0;vexs[i].vex;i++) if(vexs[i].ecno==ec2) vexs[i].ecno==ec1; }//merge_ec void MinSpanTree_Kruscal(Graph G,EdgeSetType &EdgeSet,CSTree &T)//求图的 最小生成树的克鲁斯卡尔算法 { Init_VexInfo(vexs,G.vexnum); ecnum=G.vexnum; //连通分量个数 while(ecnum>1) { GetMinEdge(EdgeSet,u,v); //选出最短边 if(!is_ec(vexs,u,v)) //u 和 v 属于不同连通分量 { Addto_CSTree(T,u,v); //加入到生成树中 merge_ec(vexs,vexs[u].ecno,vexs[v].ecno); //合并连通分量 ecnum--; } DelMinEdge(EdgeSet,u,v); //从边集中删除 }//while }//MinSpanTree_Kruscal void Addto_CSTree(CSTree &T,int i,int j)//把边(i,j)添加到孩子兄弟链表表示的树 T 中 { p=Locate(T,i); //找到结点 i 对应的指针 p,过程略 q=(CSTNode*)malloc(sizeof(CSTNode)); q->data=j; if(!p->firstchild) //双亲还没有孩子 p->firstchild=q; //作为双亲的第一个孩子 else //双亲已经有了孩子 { for(r=p->firstchild;r->nextsib;r=r->nextsib); r->nextsib=q; //作为双亲最后一个孩子的兄弟 } }//Addto_CSTree 分析:本算法使用一维结构体变量数组来表示等价类,每个连通分量所包含的所有 结点属于一个等价类.在这个结构上实现了初始化,判断元素是否等价(两个结点 是否属于同一个连通分量),合并等价类(连通分量)的操作