资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2016-12-26,#,2016,数据结构,Data structure,讲授：,刘斌,克鲁斯卡尔算法执行过程,常州信息职业技术学院,02,教,学,目标,1,克鲁斯卡尔的执行过程,03,三、链表的插入,04,克鲁斯卡尔算法执行过程,1.4,克鲁斯卡尔算法,求最小生成树,对图,5-16,的连通网,G10,，使用克鲁斯卡尔算法求最小生成树,T,的执行过程如图,5-18(a)(f),。其中：用实线表示属于,TE,的边，实线边的两个顶点均属于,U,，虚线表示不属于,TE,的边，虚线边的两个顶点一端属于,U,，另一端属于,V-U,。,V0,V3,V1,V5,V4,V2,5,6,2,6,3,6,4,7,5,1,图,5-16,连通网,G10,05,克鲁斯卡尔算法执行过程,1.4,执行过程,假设边数组,Edge,的排序结果为：,Edge0=(v0,v2,1),，,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,，亦即各顶点均不在同一个连通分量上。,V0,V3,V1,V5,V4,V2,V0,V3,V1,V5,V4,V2,5,6,2,6,3,6,4,7,5,1,06,克鲁斯卡尔算法执行过程,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),。,V0,V3,V1,V5,V4,V2,1,V0,V3,V1,V5,V4,V2,5,6,2,6,3,6,4,7,5,1,07,克鲁斯卡尔算法执行过程,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),。,V0,V3,V1,V5,V4,V2,1,2,V0,V3,V1,V5,V4,V2,5,6,2,6,3,6,4,7,5,1,08,克鲁斯卡尔算法执行过程,1.4,同样方法，取边,Edge2=(v1,v4,3),加入,TE,后，,CCNum0=0,，,CCNum1=1,，,CCNum2=0,，,CCNum3=3,，,CCNum4=1,，,CCNum5=3,。,V0,V3,V1,V5,V4,V2,1,2,3,执行过程,V0,V3,V1,V5,V4,V2,5,6,2,6,3,6,4,7,5,1,09,克鲁斯卡尔算法执行过程,1.4,取边,Edge3=(v2,v5,4),加入,TE,后，,CCNum0=0,，,CCNum1=1,，,CCNum2= 0,，,CCNum3=0,，,CCNum4=1,，,CCNum5=0,。,V0,V3,V1,V5,V4,V2,1,2,3,4,执行过程,V0,V3,V1,V5,V4,V2,5,6,2,6,3,6,4,7,5,1,10,克鲁斯卡尔算法执行过程,1.4,选取边,Edge4=(v0,v3,5),，求得顶点,v0,，,v3,在顶点表,G-vexs,中的下标分别为,0,3,，而,CCNum0=CCNum3=0,，所以舍去此边。再选取边,Edge5=(v1,v2,5),可将其加入,TE,，此后标志数组,CCNum,各元素的值均为,1,，说明所有顶点均在同一个连通分量上，算法结束，此时,TE,便是连通网,G,最小生成树的边集,。,V0,V3,V1,V5,V4,V2,1,2,3,4,5,V0,V3,V1,V5,V4,V2,5,6,2,6,3,6,4,7,5,1,THANKS,2016.9.18,
展开阅读全文