文档介绍：2016数据结构Datastructure讲授:刘斌克鲁斯卡尔算法执行过程常州信息职业技术学院02教学目标1克鲁斯卡尔的执行过程03三、-16的连通网G10,使用克鲁斯卡尔算法求最小生成树T的执行过程如图5-18(a)~(f)。其中:用实线表示属于TE的边,实线边的两个顶点均属于U,虚线表示不属于TE的边,虚线边的两个顶点一端属于U,另一端属于V-U。V0V3V1V5V4V25626364751图5-:Edge[0]=(v0,v2,1),Edge[1]=(v3,v5,2),Edge[2]=(v1,v4,3),Edge[3]=(v2,v5,4),Edge[4]=(v0,v3,5),Edge[5]=(v1,v2,5),Edge[6]=(v0,v1,6),Edge[7]=(v2,v4,6),Edge[8]=(v4,v5,6),Edge[9]=(v2,v3,7)。初始时,V={v0,v1,v2,v3,v4,v5},TE=Φ,um每个元素的初值依次为:0,1,2,3,4,5,即顶点v0,v1,v2,v3,v4,v5所在的连通分量编号依次为:0,1,2,3,4,5,亦即各顶点均不在同一个连通分量上。[0]=(v0,v2,1),求得顶点v0,v2在顶点表G->vexs中的下标分别为0,2,Num[0]=Num[2]=2标记顶点v0,v2所在的连通分量编号,由于p1!=p2,所以将边Edge[0]=(v0,v2,1)加入TE,um[2]的值改为p1,即将顶点v0,v2合并为同一个连通分量,其编号为p1=0,Num[0]=Num[1]=Num[2]=Num[3]=Num[4]=Num[5]=5。如图5-18(b)。[1]=(v3,v5,2),求得顶点v3,v5在顶点表G->vexs中的下标分别为3,5,Num[3]=Num[5]=5标记顶点v3,v5所在的连通分量编号,由于p1!=p2,所以将边Edge[1]=(v3,v5,2)加入TE,um[5]的值改为p1,即将顶点v3,v5合并为同一个连通分量,其编号为p1=3,Num[0]=Num[1]=Num[2]=Num[3]=Num[4]=Num[5]=3。如图5-18(c)。,取边Edge[2]=(v1,v4,3)Num[0]=Num[1]=Num[2]=Num[3]=Num[4]=Num[5]=3。[3]=(v2,v5,4)Num[0]=Num[1]=Num[2]=Num[3]=Num[4]=Num[5]=0。[4]=(v0,v3,5),求得顶点v0,v3在顶点表G->vexs中的下标分别为0,3,um[0]=CCNum[3]=0,所以舍去此边。再选取边Edge[5]=(v1,v2,5),可将其加入TE,um各元素的值均为1,说明所有顶点均在同一个连通分量上,算法结束,此时TE便是连通网G最小生成树的边集。V0V3V1V5V4V212345V0V3V1V5V4V25626364751