如何找到包含给定边的最小生成树？

Question

在一个带权无向图中，我需要找到包含给定边'e'的最小生成树，如果可能的话。我该怎么做？从'e'开始使用Kruskal算法吗？

- zeusm

---

是的，例如Prim也可以。 - Nico Schertler

Answer 1

我不建议使用Kruskal算法，因为如果边e是一个循环中的一部分且e在该循环中具有最大权重，则该算法将不包括'e'。我相信经过修改后它可以工作，但Prim算法的修改要求最小。

Prim算法最适合这个问题，如果我们回想一下Prim算法的步骤：

第1步：从包含随机选定顶点的集合S开始。

第2步：从所有具有一个顶点在集合S中，另一个顶点在集合V-S中的边中选择具有最小权重的边。(x,y)，其中x属于S，y属于V-S。

第3步：将y添加到集合S中。

第4步：重复步骤2和3，直到S包含所有顶点。

需要修改的地方：

对于您的问题，只需更改第1步为：

第1步：从包含边“e”=（u，v）的顶点u和v开始集合S。

- Sumeet

---

我同意Prim算法是最好的方法，但我认为Kruskal算法也可以。在Kruskal算法中，您永远不需要删除已添加的边，因此您可以从给定的边开始并继续执行。 - Edward Doolittle

@EdwardDoolittle 看来你说得对，但是 Prim 算法需要最小的修改，所以我写了它。 - Sumeet

如果边“e”是环的一部分，并且具有该环内所有边中的最大权重，则DFS测试肯定会失败，那么Kruskal或Prim都无法给您所需的MST。 - Sumeet

让我们在聊天中继续这个讨论。 - zeusm

有人能解释一下为什么在这种情况下 O(m + n) + O(mlogm) 是 O(mlogm) 吗？ - zeusm

Answer 2

以下是一个可能的“懒惰解决方案”，不需要修改MST算法：

1. 运行任何 MST算法。 - MST算法将输出一个MST T = (V,E,w) 2. 如果边e已经在T中，则完成。 3. 如果边e不在T中，则添加边e，你将得到一个循环σ。 4. 遍历循环σ，如果有一条与e相同权重的边，则删除该边并完成。 5. 如果没有边与e的权重相同，则不可能存在带有e的MST。

这种方法的好处在于它相当容易正式证明，因此您可以为MST算法提供证明，并且其他步骤基于已知定理。

- Micael Illos

---

你如何证明它？ - Kavar Rushikesh

我可以想到一个证明。如果你在最小生成树中添加边，然后移除由添加边所创建的环中权重最高的边，你将得到包含添加边的最佳最优跨度。我们称这棵树为T。考虑T上的路径P，在添加P上的边之后，添加的边将比路径P上的任何边都具有更高的权重。（可以通过反证法证明）。那么，如何改进T的权重，其中每次添加边都没有相应的反向边可从创建的环中移除，该反向边的权重比添加的边更高！！ :) 因此，T是最优的。有什么疑问吗？ - Kavar Rushikesh

Answer 3

对于一种懒惰的解决方案，使该边的成本小于所有其他边的成本，并在其上运行任何最小生成树算法。

- eesiraed