algorithm - 第二最小成本生成树

Question

我正在编写一个算法来寻找第二个最小成本生成树。我的想法如下:

1. 使用 kruskals 找到最低的 MST。
2. 删除 MST 的最低成本边。
3. 对整个图再次运行 kruskals。
4. 返回新的 MST。

我的问题是:这行得通吗？有没有更好的方法来做到这一点？

Answer 1

你可以在 O(V²) 中完成。首先使用 Prim's algorithm 计算 MST (可以在 O(V²) 中完成)。

计算 max[u, v] = MST 中从 u 到 v 的(唯一)路径上的最大成本边的成本。可以在 O(V²) 中完成。

找到一条边(u, v)，它不是最小化abs(max[u, v] - weight(u, v)) 的MST 的一部分。可以在 O(E) == O(V²) 中完成。

返回 MST' = MST - {the edge that has max[u, v] weight} + {(u, v)}，这将为您提供第二好的 MST。

Here's a link伪代码和更详细的解释。