《数据结构（C语言描述）（第2版）》教学课件5-11普里姆算法执行过程

1、2016数据结构Data structure讲授：刘斌普里姆算法执行过程常州信息职业技术学院02教学目标1普里姆算法求最小生成树的过程03三、链表的插入04普里姆算法执行过程1.1V0V3V1V5V4V25626364751普里姆算法求最小生成树 对图5-16的连通网G10，使用普里姆算法求最小生成树T的执行过程如图5-17(a)(i)。其中：用实线表示属于TE的边，实线边的两个顶点均属于U，虚线表示不属于TE的边，虚线边的两个顶点一端属于U，另一端属于V-U。图5-16 连通网G1005普里姆算法执行过程1.1普里姆算法求最小生成树将顶点v0到各顶点的边及权值放入数组Edge中，并将v0加入

2、U中。此时，U=v0，TE=，Edge0=(v0,v0,0)，Edge1=(v0,v1,6)，Edge2=(v0,v2,1)，Edge3=(v0,v3,5)，Edge4=(v0,v4,)，Edge5=(v0,v5,)V0V3V1V5V4V256（a）1V0V3V1V5V4V2562636475106普里姆算法执行过程1.1在Edge中查找最小权值的边得到Edge2，k=2，即边(v0,v2,1)，将该边加入TE，顶点G-vexsk加入U，此时U=v0,v2，TE=(v0,v2,1)，Edge2=(v0,v2, 0)，其它元素未变。V0V3V1V5V4V256（b）0普里姆算法求最小生成树V0V

3、3V1V5V4V2562636475107普里姆算法执行过程1.1 新顶点v2加入U后，调整数组Edge。由于顶点v2到顶点v1的权值为5，比顶点v0到顶点v1的权值小，所以将Edge1=(v0,v1,6) 调整为Edge1=(v2,v1, 5)，同样将Edge4=(v0,v4,)，Edge5=(v0,v5,)分别调整为Edge4=(v2,v4,6)，Edge5=(v2,v5,4) ，而顶点v2到顶点v3的权值为7，不比顶点v0到顶点v3的权值小，所以无需调整Edge3=(v0,v3,5)，调整后的情况为：Edge0=(v0,v0,0)，Edge1=(v2,v1,5)，Edge2=(v0,v2

4、,0)，Edge3=(v0,v3,5)，Edge4=(v2,v4,6)，Edge5=(v2,v5,4)。V0V3V1V5V4V255（c）640V0V3V1V5V4V2562636475108普里姆算法执行过程1.1再在Edge中查找最小权值的边得到Edge5，k=5，即边(v2,v5,4)，将该边加入TE，顶点G-vexsk加入U，此时U=v0,v2,v5，TE=(v0,v2,1), (v2,v5,4)， Edge5=(v2,v5, 0)，其它元素未变。V0V3V1V5V4V255（d）600普里姆算法求最小生成树V0V3V1V5V4V2562636475109普里姆算法执行过程1.1新顶点

5、v5加入U后，调整数组Edge。由于顶点v5到顶点v3的权值为2，比顶点v0到顶点v3的权值小，所以将Edge3=(v0,v3,5) 调整为Edge3=(v5,v3, 2)，其它均无需调整，调整后的情况为：Edge0=(v0,v0,0)，Edge1=(v2,v1,5)，Edge2=(v0,v2,0)，Edge3=(v5,v3,2)，Edge4=(v2,v4,6)，Edge5=(v2,v5,0)。V0V3V1V5V4V225（e）600V0V3V1V5V4V2562636475110普里姆算法执行过程1.1再在Edge中查找最小权值的边得到Edge3，k=3，即边(v5,v3,2)，将该边加入T

6、E，顶点G-vexsk加入U，此时U=v0,v2,v5,v3，TE=(v0,v2,1), (v2,v5,4) , (v5,v3,2)，Edge3=(v5,v3, 0)，其它元素未变。如图5-17(f)。新顶点v3加入U后，无需调整数组Edge。 V0V3V1V5V4V205（f）600V0V3V1V5V4V25626364751三、链表的插入11普里姆算法执行过程1.1再在Edge中查找最小权值的边得到Edge1，k=1，即边(v2,v1,5)，将该边加入TE，顶点G-vexsk加入U，此时U=v0,v2,v5,v3,v1，TE=(v0,v2,1), (v2,v5,4) , (v5,v3,2)

7、 , (v2,v1,5)，Edge1=(v2,v1, 0)，其它元素未变。V0V3V1V5V4V200（g）600普里姆算法求最小生成树V0V3V1V5V4V2562636475112普里姆算法执行过程1.1新顶点v1加入U后，调整数组Edge。由于顶点v1到顶点v4的权值为3，比顶点v2到顶点v4的权值小，所以将Edge4=(v2,v4,6) 调整为Edge4=(v1,v4, 3)，其它均无需调整，调整后的情况为：Edge0=(v0,v0,0)，Edge1=(v2,v1,0)，Edge2=(v0,v2,0)，Edge3=(v5,v3,0)，Edge4=(v1,v4,3)，Edge5=(v2,v5,0)。V0V3V1V5V4V200（h）300V0V3V1V5V4V2562636475113普里姆算法执行过程1.1 再在Edge中查找最小权值的边得到Edge4，k=4，即边(v1,v4,3)，将该边加入TE，顶点G-vexsk加入U，此时U=v0,v2,v5,v3,v1,v4，TE=(v0,v2,1), (v2,v5,4) , (v5,v3,2