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

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 步将导致生成另一棵生成树，比所提出的算法生成的更好。