设计一种算法，该算法采用加权图 G 并找到对非 MST 边的成本的最小变化，该变化会导致 G 的最小生成树发生变化。
到目前为止我的解决方案（需要建议）：
要更改 MST，我们需要更改非 MST 边 st 的权重，使其比 MST 中起始顶点和结束顶点路径中的最大边小 1。
所以我们可以从遍历 MST 的边开始，对于每个顶点，检查是否有非 MST 边。如果有，可以执行到达边缘端点（在 MST 中）的 bfs。非 MST 边缘权重必须更新为比路径中的最大边缘权重小一。
这将导致非 MST 边缘包含在 MST 中，并且之前的最大边缘从 MST 中删除。
有人可以判断这个解决方案是否正确？谢谢。
你找到了这个主意。但是，需要调整您的答案以表明您想要找到最小的变化，而不是您想要修改您在步行中遇到的每个非 MST 边缘。
如果这是一个学校问题，您还将被要求提供正确性证明。为了构建它，我建议依靠 Kruskal 的证明，并解释为什么您的更改会让 Kruskal 选择修改后的边缘而不是路径中的其他最大权重边缘。
我有个主意。所以基本上，我们可以遵循 Kruskal 算法的思想。所以如果我们想让MST发生变化，那么Krukal算法一定有一次没有选择原始MST中的边。该边必须是我们要修改其成本的边。所以算法很清楚。遵循克鲁斯卡尔算法，每次我们想选择一条新边e时，我们都按照克鲁斯卡尔算法不断搜索，找到另一条边e'，但仍然没有形成循环。然后我们计算成本的最小变化：w(e')-w(e)-1 。（我不确定成本是否限制为整数）。只需从上面选择最小的变化。