更改为图中非MST边缘以更改MST

Question

设计一个算法，该算法采用加权图G，并找到非MST边缘的成本中的最小变化，这将导致生成最小生成树的最小生成树G.

我的解决方案至今（需要建议）：

若要更改为MST，我们需要改变非MST边缘ST的重量它比MST中其起始顶点和结束顶点的路径中的最大边缘小1。因此，我们可以先步行MST的边缘，并为每个顶点检查是否存在非MST边缘。如果有，可以完成一个bfs到达边缘的终点（在MST中）。非MST边权重必须更新为小于路径中最大边权重的值。

这将导致非MST边缘被包括在MST中，并且先前的最大边缘将被从MST中移除。

有人可以告诉这个解决方案是否正确？谢谢。

Answer 1

您发现了这个想法。 但是，您的答案需要进行调整，以表明您希望找到最小更改，而不是要修改在步行中遇到的每个非MST边缘。

如果这是一个学校问题，你也会被要求提供一个正确的证明。为了建立它，我建议依靠克鲁斯卡尔的证明，并解释为什么你的改变会让克鲁斯卡尔选择修改的边而不是路径中的其他最大权重边。

Answer 2

我有个主意。所以基本上，我们可以遵循Kruskal算法的思想。所以如果我们想要改变MST，那么肯定有一次Krukal算法不会选择原始MST中的边缘。该边缘必须是我们要修改的边缘。所以算法很清楚。按照Kruskal算法，每当我们想要选择一个新的边e时，我们继续按照克鲁斯卡尔算法进行搜索，并找到仍然没有创建循环的另一个边e'。然后我们计算成本的最小变化：w（e'） - w（e）-1。（我不确定成本是否限制为一个整数）。只需从上面选择最小变化。