algorithm - 在图中查找 O(V+E) 时间的 MST

Question

以前曾问过类似的问题，如 https://cs.stackexchange.com/questions/28635/find-an-mst-in-a-graph-with-edge-weights-from-1-2

问题是:给定一个连通的无向图 G=(V,E) 和一个权重函数 w:E→{1,2}，提出一种不使用 Kruskal 在 O(V+E) 中找到图的 MST 的有效算法。

我查看了上面线程中建议的解决方案，但我仍然不确定如何让它发挥作用。第一个建议不考虑组件。第二个建议没有提供更多关于如何识别新考虑的边缘如果添加到当前 MST 是否会形成循环的详细信息。棘手的部分是如何在线性时间内识别两个顶点是否在同一组件中。

我目前的想法是

1. 对顶点进行排序，可以在线性时间内完成
2. 首先考虑权重为 1 的边。当边数小于或等于|V1|-1时，将边添加到MST。 V1 是边上权重为 1 的顶点。我们需要确保检查所有权重为 1 的顶点。哈希集可用于存储 V1 和边。
3. 使用相同的逻辑将 V2 添加到图中。

如果我的想法有缺陷，谁能提出建议？如果是这样，解决这个问题的最佳方法是什么？非常感谢!

Answer 1

我建议你做类似给定问题中第二个答案的事情:

这是 prim 的算法:

Start by picking any vertex to be the root of the tree.

While the tree does not contain all vertices in the graph find shortest edge leaving the tree and add it to the tree .

所以现在，如果我们可以在 O(1) 时间内在离开树的边集中执行查找，并且我们可以保持集合更新，那么搜索总是可以在总 O(|E|) 时间的恒定时间内发生, 那么我们就可以开始了。

现在要实现这一点，请将离开树的边集想象成一个链表。现在每当一个顶点被添加到形成 MST 的顶点集合时，遍历它的邻接列表并将权重 1 的边添加到列表的前面，并将权重 2 的边添加到列表的末尾。现在，只要您想要离开树的最小边，只需从链表的前面取一条!

此方法的唯一问题是您应该只将“离开树”的边添加到列表中!因为如果我们不这样做，我们可能最终会出现循环!为了检查每条边的这个“离开树”属性，我们可以使用选定顶点的集合，我们可以在添加之前检查每条边，它没有两端都在集合中，所以当你添加新添加的顶点的边到离开树的边集，首先检查边的另一端的顶点是否在树的选定顶点集中，并且仅当另一条边不在时才将边添加到列表中t 在集合中。您可以在 O(1) 时间内检查集合中元素是否存在，这样就不会出现循环!