8

我从 Robert Sedgewick 的算法书中得到了这个问题。

临界边缘。从图中删除会导致 MST 权重增加的 MST 边称为临界边。展示如何在与 E log E 成比例的时间内找到图中的所有关键边。注意：这个问题假设边权重不一定不同（否则 MST 中的所有边都是关键的）。

请提出解决此问题的算法。

我能想到的一种方法可以及时完成工作 EV 我的方法是运行 kruskal 算法。

但是每当我们遇到一条边，它在 MST 中的插入创建了一个循环，并且如果该循环已经包含具有相同边权重的边，那么，已经插入的边将不是关键边（否则所有其他 MST 边都是关键边） .

这个算法正确吗？我怎样才能扩展这个算法来及时完成 E log E 的工作。

4

2 回答 2

7

我认为您建议的边缘至关重要时的条件是正确的。但是没有必要实际找到一个循环并测试它的每个边缘。

The Kruskal algorithm adds edges in increasing weight order, so the sequence of edge additions can be broken into blocks of equal-weight edge additions. Within each equal-weight block, if there is more than one edge that joins the same two components, then all of these edges are non-critical, because any one of the other edges could be chosen instead. (I say they are all non-critical because we are not actually given a specific MST as part of the input -- if we were then this would identify a particular edge to call non-critical. The edge that Kruskal actually chooses is just an artefact of initial edge ordering or how sorting was implemented.)

But this is not quite sufficient: it might be that after adding all edges of weight 4 or less to the MST, we find that there are 3 weight-5 edges, connecting component pairs (1, 2), (2, 3) and (1, 3). Although no component pair is joined by more than 1 of these 3 edges, we only need (any) 2 of them -- using all 3 would create a cycle.

For each equal-weight block, having weight say w, what we actually need to do is (conceptually) create a new graph in which each component of the MST so far (i.e. using edges having weight < w) is a vertex, and there is an edge between 2 vertices whenever there is a weight-w edge between these components. (This may result in multi-edges.) We then run DFS on each component of this graph to find any cycles, and mark every edge belonging to such a cycle as non-critical. DFS takes O(nEdges) time, so the sum of the DFS times for each block (whose sizes sum to E) will be O(E).

Note that Kruskal's algorithm takes time O(Elog E), not O(E) as you seem to imply -- although people like Bernard Chazelle have gotten close to linear-time MST construction, TTBOMK no one has got there yet! :)

于 2013-03-30T18:57:59.260 回答
5

是的，你的算法是正确的。我们可以通过比较 Kruskal 算法的执行与类似的执行来证明，其中一些 MST 边 e 的成本变为无穷大。在第一次执行考虑 e 之前，两次执行都是相同的。在 e 之后，第一次执行的连通分量比第二次少一个。这种情况一直持续到边缘 e' 被认为在第二次执行中加入了 e 将具有的组件。由于边 e 是迄今为止构建的森林之间的唯一区别，因此它必须属于由 e' 创建的循环。在 e' 之后，执行做出相同的决定，森林中的不同之处在于第一个执行有 e，第二个执行有 e'。

实现此算法的一种方法是使用动态树，这是一种表示标记森林的数据结构。此 ADT 的一种配置支持以下对数时间方法。

  • MakeVertex() - 构造并返回一个新的顶点。
  • Link(u, c, v) - 顶点 u 和 v 不得连接。创建从顶点 u 到顶点 v 的无标记边，成本为 c。
  • Mark(u, v) - 顶点 u 和 v 必须是边 e 的端点。标记 e。
  • Connected(u, v) - 表示顶点 u 和 v 是否连接。
  • FindMax(u, v) - 顶点 u 和 v 必须连接。返回从 u 到 v 的唯一路径上具有最大成本的未标记边的端点以及该成本。该边的端点按照它们出现在路径上的顺序给出。

我没有声称这在实践中是一个很好的算法。动态树，如瑞士军刀，用途广泛但复杂，通常不是完成这项工作的最佳工具。我鼓励您考虑如何利用这样一个事实，即我们可以等到所有边缘都被处理后才能确定关键边缘是什么。

于 2013-03-30T18:24:21.737 回答