algorithm - 无向图中的 MST

Question

我有一个无约束图 G=(V,E) 和权重函数 w:E->R+。另外，我有 G 的 MST T。

我必须构建一个执行以下操作的算法:
如果我们向 E 添加一个具有权重 w(e') 的新边 e'。建议一种更新 T 的算法，它将成为新图 G'=(V,EUe') 的 MST。
复杂度:O(V)。

我的建议是:

1) 将 e' 添加到 T。我们得到一个名为 T' 的新图，其中包含一个循环。
2) 在 T' 上运行 DFS 并标记您访问的每个顶点。并且另外保存
堆栈中的每个顶点和每个边缘权重。
3) 当我们访问一个我们已经访问过的顶点时，我们停止运行。
4) 然后开始从堆栈中退出，直到我们到达我们停止的顶点。
5)在撤回时，我们保存从中撤回的最大边缘权重 堆栈。
6) 如果最大边缘权重大于 w(e') 我们替换它们。
7) 否则我们保持相同的 T。

我希望一切都清楚。
如果有人能告诉我它是否有效或给我其他的，我将不胜感激
解决方案和建议。

Answer 1

是的，您建议的解决方案是正确的，因为具有相同数量的边和节点(如 T)的图由一个简单的循环组成，其中的树以该循环的某些(可能没有)节点为根。

您需要从 T 中恰好删除 1 条边，这样剩余的图仍然是连通的。显然最好的选择是删除最大的边。您可以在保持图形连接的同时删除的唯一边是循环中的边(您要添加到堆栈的边)。

另一个解决方案是找到 bridges在图中，然后找到最大的非桥边并将其删除。然而，由于这是一个特殊的图，您提到的解决方案会容易得多(非桥边是循环中的边)。