《数据结构（C语言描述）（第2版）》教学课件5-14克鲁斯卡尔算法执行过程

1、2016数据结构Data structure讲授：刘斌克鲁斯卡尔算法执行过程常州信息职业技术学院02教学目标1克鲁斯卡尔的执行过程03三、链表的插入04克鲁斯卡尔算法执行过程1.4克鲁斯卡尔算法求最小生成树对图5-16的连通网G10，使用克鲁斯卡尔算法求最小生成树T的执行过程如图5-18(a)(f)。其中：用实线表示属于TE的边，实线边的两个顶点均属于U，虚线表示不属于TE的边，虚线边的两个顶点一端属于U，另一端属于V-U。V0V3V1V5V4V25626364751图5-16 连通网G1005克鲁斯卡尔算法执行过程1.4执行过程 假设边数组Edge的排序结果为：Edge0=(v0,v2,1)

2、，Edge1=(v3,v5,2)，Edge2=(v1,v4,3)，Edge3=(v2,v5,4)，Edge4=(v0,v3,5)，Edge5=(v1,v2,5) ，Edge6=(v0,v1,6)，Edge7=(v2,v4,6)，Edge8=(v4,v5,6) ，Edge9=(v2,v3,7)。 初始时，V=v0,v1,v2,v3,v4,v5，TE=，标志数组CCNum每个元素的初值依次为：0,1,2,3,4,5，即顶点v0,v1,v2,v3,v4,v5所在的连通分量编号依次为：0,1,2,3,4,5，亦即各顶点均不在同一个连通分量上。V0V3V1V5V4V2V0V3V1V5V4V2562636

3、475106克鲁斯卡尔算法执行过程1.4 选取边Edge0=(v0,v2,1)，求得顶点v0，v2在顶点表G-vexs中的下标分别为0,2，分别用p1=CCNum0=0和p2=CCNum2=2标记顶点v0，v2所在的连通分量编号，由于p1!=p2，所以将边Edge0=(v0,v2,1)加入TE，并将连通分量编号为p2的所有元素CCNum2的值改为p1，即将顶点v0，v2合并为同一个连通分量，其编号为p1=0，此时，CCNum0=0，CCNum1=1，CCNum2=0，CCNum3=3，CCNum4=4，CCNum5=5。如图5-18(b)。V0V3V1V5V4V21V0V3V1V5V4V256

4、2636475107克鲁斯卡尔算法执行过程1.4选取边Edge1=(v3,v5,2)，求得顶点v3，v5在顶点表G-vexs中的下标分别为3,5，分别用p1=CCNum3=3和p2=CCNum5=5标记顶点v3，v5所在的连通分量编号，由于p1!=p2，所以将边Edge1=(v3,v5,2)加入TE，并将连通分量编号为p2的所有元素CCNum5的值改为p1，即将顶点v3，v5合并为同一个连通分量，其编号为p1=3，此时，CCNum0=0，CCNum1=1，CCNum2=0，CCNum3=3，CCNum4=4，CCNum5=3。如图5-18(c)。V0V3V1V5V4V212V0V3V1V5V4

5、V2562636475108克鲁斯卡尔算法执行过程1.4同样方法，取边Edge2=(v1,v4,3) 加入TE后，CCNum0=0，CCNum1=1，CCNum2=0，CCNum3=3，CCNum4=1，CCNum5=3。V0V3V1V5V4V2123执行过程V0V3V1V5V4V2562636475109克鲁斯卡尔算法执行过程1.4取边Edge3=(v2,v5,4) 加入TE后，CCNum0=0，CCNum1=1，CCNum2= 0，CCNum3=0，CCNum4=1，CCNum5=0。V0V3V1V5V4V21234执行过程V0V3V1V5V4V2562636475110克鲁斯卡尔算法执行过程1.4选取边Edge4=(v0,v3,5)，求得顶点v0，v3在顶点表G-vexs中的下标分别为0,3，而CCNum0=CCNum3=0，所以舍去此边。再选取边Edge5=(v1,v2,5),可将其加入TE，此后标志数组CCNum各元素的值均为1，说明所有顶点均在同