文档介绍：2016数据结构Datastructure讲授:刘斌普里姆算法执行过程常州信息职业技术学院02教学目标1普里姆算法求最小生成树的过程03三、-16的连通网G10,使用普里姆算法求最小生成树T的执行过程如图5-17(a)~(i)。其中:用实线表示属于TE的边,实线边的两个顶点均属于U,虚线表示不属于TE的边,虚线边的两个顶点一端属于U,另一端属于V-U。图5-,并将v0加入U中。此时,U={v0},TE=Φ,Edge[0]=(v0,v0,0),Edge[1]=(v0,v1,6),Edge[2]=(v0,v2,1),Edge[3]=(v0,v3,5),Edge[4]=(v0,v4,∞),Edge[5]=(v0,v5,∞)V0V3V1V5V4V256(a)∞∞[2],k=2,即边(v0,v2,1),将该边加入TE,顶点G->vexs[k]加入U,此时U={v0,v2},TE={(v0,v2,1)},Edge[2]=(v0,v2,0),其它元素未变。V0V3V1V5V4V256(b)∞∞,调整数组Edge。由于顶点v2到顶点v1的权值为5,比顶点v0到顶点v1的权值小,所以将Edge[1]=(v0,v1,6)调整为Edge[1]=(v2,v1,5),同样将Edge[4]=(v0,v4,∞),Edge[5]=(v0,v5,∞)分别调整为Edge[4]=(v2,v4,6),Edge[5]=(v2,v5,4),而顶点v2到顶点v3的权值为7,不比顶点v0到顶点v3的权值小,所以无需调整Edge[3]=(v0,v3,5),调整后的情况为:Edge[0]=(v0,v0,0),Edge[1]=(v2,v1,5),Edge[2]=(v0,v2,0),Edge[3]=(v0,v3,5),Edge[4]=(v2,v4,6),Edge[5]=(v2,v5,4)。V0V3V1V5V4V255(c)[5],k=5,即边(v2,v5,4),将该边加入TE,顶点G->vexs[k]加入U,此时U={v0,v2,v5},TE={(v0,v2,1),(v2,v5,4)},Edge[5]=(v2,v5,0),其它元素未变。V0V3V1V5V4V255(d),调整数组Edge。由于顶点v5到顶点v3的权值为2,比顶点v0到顶点v3的权值小,所以将Edge[3]=(v0,v3,5)调整为Edge[3]=(v5,v3,2),其它均无需调整,调整后的情况为:Edge[0]=(v0,v0,0),Edge[1]=(v2,v1,5),Edge[2]=(v0,v2,0),Edge[3]=(v5,v3,2),Edge[4]=(v2,v4,6),Edge[5]=(v2,v5,0)。V0V3V1V5V4V225(e)[3],k=3,即边(v5,v3,2),将该边加入TE,顶点G->vexs[k]加入U,此时U={v0,v2,v5,v3},TE={(v0,v2,1),(v2,v5,4),(v5,v3,2)},Edge[3]=(v5,v3,0),其它元素未变。如图5-17(f)。新顶点v3加入U后,无需调整数组Edge。V0V3V1V5V4V205(f)600V0V3V1V5V4V25626364751