minimum-spanning-tree - 向图中添加新边并找到新的生成树

Question

假设我们给出了给定图 G 的最小生成树 T(有 n 个顶点和 m 个边)和一条权重为 w 的新边 e = (u, v)，我们将添加到 G 中。

I) 检查 T 是否仍然是 MST。II) 如果不是，请给出一个有效的算法来找到图 G + e 的最小生成树。

Answer 1

您当前的 MST T包含n-1边缘。添加到新边的图表中 e = (u,v)重量 w创建恰好一个周期C图中T + e (T 添加了边缘 e)。如果新的边权重( w )小于本次循环中权重最高的边的权重 C ，那么您可以通过将较高权重的边替换为 e 来创建较低权重的 MST 。否则，您当前的 MST 仍保持最佳状态。

算法基本上是这样的:

1. 找到唯一路径P来自u至v在T
2. 找到边缘 e*在P具有最大权重 w*
3. 是w < w* ？
   • 如果是这样，那么T' = T - e* + e是 G + e 的 MST ，
     与weight(T') = weight(T) - w* + w
   • 如果没有，则T' = T是 G + e 的 MST