Prim：每轮接入一个最近的外部顶点
从 A 出发；`lowCost[v]` 表示外部顶点 v 到当前树集合的最小边权。
上一页
下一页
1
2
2
3
1
2
1
2
4
A
B
C
D
E
F
1. 初始树集合 {A}
外部顶点
B
C
D
E
F
lowCost
1(A)
2(A)
∞
∞
∞
选择 `lowCost` 最小的外部顶点 B，将边 AB 加入生成树。
2. 接入 B，更新 lowCost
外部顶点
C
D
E
F
lowCost
2(A)
3(B)
∞
∞
B 的邻接边只会影响仍在树外的顶点。当前最小值是 C 的 2，下一轮接入 C。
3. 接入 C，更新 lowCost
外部顶点
D
E
F
lowCost
3(B)
1(C)
4(C)
C 使 E 的接入代价变为 1，这是当前最小值，因此下一轮接入 E。
4. 接入 E，更新 lowCost
外部顶点
D
F
lowCost
2(E)
2(E)
D 与 F 的最小接入代价同为 2。本例按顶点字母顺序处理并接入 D。
5. 接入 D，更新 lowCost
外部顶点
F
lowCost
1(D)
只剩一个外部顶点时，按当前最小接入边将其加入生成树。
6. Prim 生成树完成
选中边为 AB、AC、CE、DE、DF，总权值为 1+2+1+2+1=7。它是一棵最小生成树。
方向键可翻页