3 
 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(V E)。由于它在 O(logV) 循环内，因此得到 O(logV V*E)。

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

4

1 回答 1

2

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

- 编辑 -

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

于 2010-07-28T08:09:53.283 回答