Kruskal：同一图上的边筛选
等权边排序可不同；每条边都要先判断加入后是否成环。
上一页
下一页
1
2
2
3
1
2
1
2
4
A
B
C
D
E
F
1. 排序后从最小边开始
AB:1
CE:1
DF:1
AC:2
BC:2
EF:2
DE:2
BD:3
CF:4
初始每个顶点自成一个集合：
{A} {B} {C} {D} {E} {F}
。Kruskal 先看权值，再看是否会成环。
2. 选择 AB:1
AB:1
CE:1
DF:1
AC:2
BC:2
EF:2
A 与 B 不在同一集合，选入 AB。集合变为
{A,B} {C} {D} {E} {F}
。
3. 选择 CE:1
AB:1
CE:1
DF:1
AC:2
BC:2
EF:2
C 与 E 不在同一集合，选入 CE。集合变为
{A,B} {C,E} {D} {F}
。
4. 选择 DF:1
AB:1
CE:1
DF:1
AC:2
BC:2
EF:2
D 与 F 不在同一集合，选入 DF。集合变为
{A,B} {C,E} {D,F}
。
5. 选择 AC:2
AB:1
CE:1
DF:1
AC:2
BC:2
EF:2
A 与 C 分属两个集合，选入 AC。集合变为
{A,B,C,E} {D,F}
。
6. 检查 BC:2，但跳过
AB:1
CE:1
DF:1
AC:2
BC:2
EF:2
B 与 C 已经通过 B-A-C 连通。虽然 BC 的权值只有 2，但加入它会形成 A-B-C-A 回路，所以跳过。
7. 选择 EF:2，生成树完成
AB:1
CE:1
DF:1
AC:2
BC:2
EF:2
E 与 F 分属两个集合，选入 EF。已选 5 条边，等于 n-1，生成树完成。
8. Kruskal 得到另一棵 MST
Kruskal 选中 AB、CE、DF、AC、EF，总权值为 1+1+1+2+2=7。它与 Prim 示例树不同，但总代价同样最小。
方向键可翻页