寻找最小生成树的所有关键边

Question

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

关键边。一个最小生成树边，如果从图中删除它将导致MST权重增加，则称为关键边。请展示如何在时间上与E log E成比例地找到图中的所有关键边。注意：此问题假设边权不一定不同（否则MST中的所有边都是关键边）。

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

我能想到的一种方法可以在时间E.V内完成任务。我的方法是运行Kruskal's算法。

但是，每当我们遇到一条插入MST的边会创建一个循环，如果该循环已经包含具有相同边权的边，则已插入的边将不是关键边（否则，所有其他MST边都是关键边）。

这个算法正确吗？如何扩展此算法以在时间E log E内完成任务？

- Nikunj Banka

Answer 1

你提出的关于边缘何时被认为是关键的条件是正确的。但并不需要实际查找一个循环并测试每个边缘。

Kruskal算法按增加的权重顺序添加边缘，因此边缘添加的顺序可以分成相等权重边缘添加的块。在每个相等权重块中，如果有多于一条连接同两组分的边缘，则所有这些边缘都是非关键的，因为其他任何一条边缘都可以选择。（我说它们都是“非关键的”是因为我们没有实际给定作为输入的特定MST——如果有的话，这将确定一条具体的边缘称为非关键的。Kruskal实际选择的边缘仅是初始边缘排序或排序方式的产物。）

但这还不够：在向MST添加所有权重小于4的边缘之后，可能会发现有3条权重为5的边缘，连接着组件对(1,2)、(2,3)和(1,3)。虽然没有任何组件对被3条中的任意一条以上的边缘连接，但我们只需要其中的2条——使用全部3条将创建一个循环。

对于每个相等权重块，例如w，我们实际上需要做的是（概念上）创建一个新图，在这个图中，迄今为止MST的每个组件（即使用权重小于w的边缘）都是一个顶点，并且当这些组件之间有一个权重为w的边缘时，就会在两个顶点之间形成一条边缘。（这可能会导致多重边缘。）然后我们对该图的每个组件运行DFS以查找任何循环，并将属于这样的循环的每个边缘标记为非关键的。DFS需要O(nEdges)时间，因此每个块的DFS时间之和（它们的大小之和为E）将为O(E)。

请注意，Kruskal算法的时间复杂度为O(ElogE)，而不是您所暗示的O(E)——尽管像Bernard Chazelle这样的人已经接近线性时间MST构造，但据我所知，还没有人达到那里！：）

- j_random_hacker

---

我不明白为什么dfs时间的总和会是O(E)。考虑这个图http://i.imgbox.com/RdXix9x4.png难道dfs不会分别在Kruskal算法的第3步遍历3、5、7、9、11个顶点吗？对于稀疏图，这将导致至少O(V^2)的额外时间（我不确定如何生成E << V^2图以获得O(EV)的情况，但我认为这是可能的）。对于稠密图，dfs将被调用O(E - (V-1)) ~ O(V^2)次，其成本为O(V)，因此总的额外复杂度将是O(V^3)，这根本不是O(ElogE)。也许我哪里错了？ - Ralor

这里是针对稠密图的糟糕测试 http://i.imgbox.com/hbWvMRmg.png抱歉打扰了，不过我正在寻找ElogV解决方案（实际上这是Sedgewick书中提出的问题） - Ralor

@Ralor：我对DFS时间总和的O(E)估计有些错误，因为您还需要时间来维护“组件图”（每个顶点是MST-so-far的一个组件，每条边是原始图中的一条权重为w的边），这需要至少每个操作的反阿克曼时间。 （处理原始图中相等权重边的每个块会导致某些顶点子集在组件图中合并，并提取一组新的边缘子集。）之后，请注意，原始图中的每条边都将被DFS正好访问一次。 - j_random_hacker

Answer 2

是的，你的算法是正确的。我们可以通过比较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的唯一路径上具有最大成本的未标记边的端点，以及该成本。这条边的端点按它们在路径上出现的顺序给出。

我不保证这在实践中是一个好算法。动态树（像瑞士军刀一样）是多才多艺但复杂的数据结构，通常并不是最适合的工具。我鼓励你思考如何利用我们可以等到所有边都被处理完才弄清楚哪些是关键边的事实。

- David Eisenstat