从加权图中找到第二好的最小生成树的算法

Question

我正在尝试从加权无向图中找到跨越三个的第二个最佳最小值。我知道如何使用 Kruskal 算法计算 MST，我想通过这种方式找到第二好的最小算法：

步骤：

1. 对所有图边进行排序。

2. 使用 Kruskal 计算 MST

3. 从图中获取不在第一个MST中的最小权重边加入MST（现在MST有环）

4. 去掉新形成的循环中的最大权重边

这应该是第二好的 MST 吧？

顺便说一下，我知道有一个主题指出了一种算法，该算法在每个 MST 边之间迭代并在没有选择边的情况下在图上运行 Kruskal，我只是想问我的是否有效。

Answer 1

没用。

在第3步之后，新添加的边可能会成为只包含成本非常低的边的循环的一部分，因此在第3步和第4步之后，MST的整体成本会显着增加。

另一方面，该图可能包含与在步骤 3 中选择的边成本相似的另一条边，当添加到 MST 中时，该边将成为另一个循环的一部分，例如，包含成本相对较高的边.为第 3 步选择这条边，然后应用第 4 步将导致生成另一棵生成树，比所提出的算法生成的生成树更好。

Answer 2

不，你的算法不起作用。

  1        3
 /--\  2  /--\
.    .---.    .
 \--/     \--/
  4        5

MST 为 1,2,3 => 6。

第二好的是 1,2,5 => 8。

您的算法将 return 2,3,4 => 9.

（我假设您的第 4 步是 return 最大权重边缘，而不是您刚刚添加的边缘）

---

这里的关键是1和4的差值（3）大于3和5的差值（2），所以用5替换3比用4替换1的总成本要低。