第二分钟成本生成树

Question

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

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

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

Answer 1

考虑这种情况:

------100----
|           |
A--1--B--3--C
      |     |
      |     3
      |     |
      2-----D

MST由ABDC(成本6)组成.第二个最低成本是ABCD(成本7).如果删除最低成本边缘,则会获得ACBD(成本105).

所以你的想法不会奏效.虽然我没有更好的想法......

Answer 2

你可以在O(V ²)中完成.首先使用Prim算法计算MST (可以在O(V ²)中完成).

计算max[u, v] = the cost of the maximum cost edge on the (unique) path from u to v in the MST.可以在O(V ²)中完成.

找到一个(u, v)不属于最小化的MST 的边缘abs(max[u, v] - weight(u, v)).可以在O(E)== O(V ²)中完成.

返回MST' = MST - {the edge that has max[u, v] weight} + {(u, v)},这将给你第二好的MST.

这是一个伪代码链接和更详细的解释.

Answer 3

您可以这样做——尝试从图中一次删除一个 MST 的边，然后运行 ​​MST，从中获取最小值。所以这与你的相似，除了迭代：

1. 使用 Kruskals 查找 MST。
2. 对于 MST 中的每条边：
   1. 从图中删除边
   2. 计算 MST 上的 MST'
   3. 跟踪最小的 MST
   4. 将边添加回图形
3. 返回最小的 MST。