algorithm - Boruvka 的算法复杂度怎么可能是 O(ElogV)？

Question

 1 Begin with a connected graph G containing edges of distinct weights, and an empty set of edges T
 2 While the vertices of G connected by T are disjoint:
 3   Begin with an empty set of edges E
 4   For each component:
 5     Begin with an empty set of edges S
 6     For each vertex in the component:
 7       Add the cheapest edge from the vertex in the component to another vertex in a disjoint component to S
 8     Add the cheapest edge in S to E
 9   Add the resulting set of edges E to T.
10 The resulting set of edges T is the minimum spanning tree of G.

来自维基百科。我知道外循环是 logV，因为你正在加入集合。但接下来是内部循环。

如果你使用等价关系来跟踪集合，这意味着你只得到代表集合的元素，所以你无法确定两个集合之间权重最小的边，因为你没有所有的元素。如果您修改结构以保存对子项的引用，您仍然必须获取每个集合的所有子项。这意味着，更坏的情况下，每个集合的 O(V/2) = O(V)。

之后，还是要找到连接两者的最小边，也就是遍历连接两个组件的所有边。因此，您需要遍历每个节点，看看它的边是否连接到另一个组件中的元素，如果是，它是否小于您当前拥有的最小边。

意思是，一个外层循环遍历节点，一个内层循环遍历节点的边缘 - O(VE)。因为它在一个 O(logV) 循环内，所以你得到 O(logVV*E)。

现在，您似乎只需要遍历所有边，但是您将如何选择 2 个分量之间的最小边？我可以判断给定的边是否连接不同组件中的节点，但我无法判断连接它们的节点的权重最小。如果我得到重量最小的那个，它可能无法连接它们。

Answer 1

如果允许哈希表，那么我会看到它如何成为 O(Elog N) 算法。每个组件都存储为不同的哈希集。最初，每个集合包含一个节点。为所有组件找到最小“桥”的步骤需要 O(E) 时间，因为我们最多检查每条边两次，并且我们假设在哈希集中进行恒定时间查找。然后我们继续合并集合，这需要 O(N) 时间。由于图是连通的，E>=N-1，因此每次迭代的总成本为 O(E)。

--编辑--

根据 throwawayacct 的评论，根本不需要散列结构。在每次迭代中，我们都有一个由前一次迭代生成的森林图，因此我们可以在 O(E) 时间内重新计算其连接的组件。例如，这可以通过从所有节点进行简单的 DFS 遍历来完成，为每个组件设置唯一的“颜色”。然后，在扫描边缘以寻找桥梁时，我们只考虑连接不同颜色节点的边缘。