通过从每个顶点选取最小边的 MST 算法？

Question

是否可以通过简单地遍历图中的顶点并选择该顶点的最小边并取所有这些边的并集来创建 MST？这似乎与切割 属性 并不矛盾，并且比实施 Prim 算法更有效。

Answer 1

Kruskal 构建 MST 的算法

1. 初始化 H = ∅.
2. 按权重递增的顺序对边进行排序。
3. 按权重递增的顺序遍历边。
   • 如果e的端点在H.
     • 将 e 添加到 H。

来源：https://www.cc.gatech.edu/~rpeng/CS3510_F17/Notes/Sep27MST.pdf

如果您简单地迭代所有边 w/o 并考虑它们是否是 MST 的一部分，那么您不能确定它们不会形成循环。

Answer 2

没有。顶点可以共享一条最小边，因此您可能无法将它们全部连接起来：

A---1---B
|       |
2       2
|       |
C---1---D

您至少需要一条权重为 2 的边来创建 MST，但它们都不是任何顶点的最小边。