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

Question

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

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

Answer 1

您当前的 MSTT包含n-1边。e = (u,v)将带有权重的新边添加到您的图形中会在图形中w创建一个循环（添加边）。如果新的边权重 ( ) 小于此循环中权重最高的边的权重，那么您可以通过将较高权重的边替换为 来创建较低权重的 MST 。否则，您当前的 MST 将保持最佳状态。CT + eTewCe

算法基本上是这样的：

1. P找到从u到v的唯一路径T
2. 找到权重最大e*的边Pw*
3. 是w < w*吗？
   • 如果是这样，那么T' = T - e* + eMST 是G + e,
     与weight(T') = weight(T) - w* + w
   • 如果不是，那么T' = T是 MSTG + e