Question

从顶点A出发，写出按普利姆算法构造下图的一棵最小生成树的过程。

Answer 1

G<-{A} , I<-{BCDEF}
I选出与G距离最近的边，这里是AF .
由于 BA=6 CA=sup DA=sup EA=5 FA=1 所以选F。

G<-{A,F} I<-{BCDE}
选出与G距离最近的边，
由于
BA=6 BF=5 ==> BG = 5
CA=sup CF=6 ==> CG=6
DA=sup DF=5 ==> DG=5
EA=5 EF=5 ==> EG=5
有三个最近的，随便选一个，这里选B .

G<-{A,B,F} I<-{CDE}
(套用上面的结果)由于

CG=6, CB=3 ==> CG=3
DG=5, DB=sup ==> DG=5

EG=5 , EB=sup ==> EG=5
选 C。

G<-{A,B,C,F} I<-{D,E}
由于
DG=5,DC=6 ==> DG=5
EG=5 ,EC=sup ==> EG=5
有二个最近的，随便选一个，这里选D

G<-{A,B,C,D,F} I<-{E}

最后一个没得选了，

G<-{A,B,C,D,E,F} I<-{}