algorithm - 更改为图中的非 MST 边以更改 MST

Question

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

到目前为止我的解决方案(需要建议):

要对 MST 进行更改，我们需要更改非 MST 边 s.t 的权重。比其起始顶点和结束顶点在MST中的路径中的最大边少1。

所以我们可以从遍历 MST 的边开始，对于每个顶点，检查是否有非 MST 边。如果存在，则可以完成到达边缘终点(在 MST 中)的 bfs。非MST边权重必须更新为比路径中的最大边权重小1。

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

有人可以判断这个解决方案是否正确吗？谢谢。

Answer 1

您找到了主意。但是，您的答案需要调整以表明您想要找到最小的变化，而不是您想要修改您在行走中遇到的每个非 MST 边缘。

如果这是一个学校问题，您还将被要求提供正确性证明。为了构建它，我建议依赖 Kruskal 的证明，并解释为什么你的更改会让 Kruskal 选择修改后的边而不是路径中的其他最大权重边。