🏷️ 知识点：Kruskal 算法

已知无向图 G 如下所示，使用克鲁斯卡尔（Kruskal）算法求图 G 的最小生成树，加入到最小生成树中的边依次是（ ）。

最小生成树

A. (b,f), (b,d), (a,e), (c,e), (b,e) B. (b,f), (b,d), (b,e), (a,e), (c,e) C. (a,e), (b,e), (c,e), (b,d), (b,f) D. (a,e), (c,e), (b,e), (b,f), (b,d)

[tag_link]

正确答案：A

Kruskal 算法 按边权递增检查边，只加入不会形成环的边。依次选 (b,f)=5、(b,d)=6；(d,f)=7 会在 b-d-f 中成环，跳过；再选 (a,e)=9、(c,e)=10、(b,e)=11，此时 6 个顶点由 5 条边连通，MST 完成。因此选 A。