无向图中的 MST
MST in unDirected graph
我有一个无约束图 G=(V,E) 和权重函数 w:E->R+。另外，我有 G 的 MST T。
我必须构建一个执行以下操作的算法：
如果我们向 E 添加一个具有权重 w(e') 的新边 e'。建议一种更新 T 的算法，它将成为新图 G'=(V,EUe').
复杂度：O(V)。
我的建议是：
1) 将 e' 添加到 T。我们得到一个名为 T' 的新图，其中包含一个循环。
2) 运行 T' 上的 DFS 并标记您访问的每个顶点。另外保存
堆栈中的每个顶点和每个边缘权重。
3) 当我们访问一个我们已经访问过的顶点时，我们停止 运行.
4) 然后开始从堆栈中退出，直到我们到达我们停止的顶点。
5）在撤回时，我们保存从中撤回的最大边缘权重
堆叠.
6) 如果最大边缘权重大于 w(e') 我们替换它们。
7) 否则我们保持相同的 T。
我希望清楚。
如果有人能帮我解决问题，或者给我其他的，我将不胜感激
解决方案和建议。
是的，您建议的解决方案是正确的，因为具有相同数量的边和节点（如 T）的图由一个简单的循环组成，树根植于此的某些（可能 none）的节点循环.
您需要从 T 中恰好删除 1 条边，这样剩余的图仍然是连通的。显然最好的选择是删除最大的边。您可以在保持图形连接的同时删除的唯一边是循环中的边（您要添加到堆栈的边）。
另一种解决方案是在图中找到bridges，然后找到最大的非桥边并将其删除。但是，由于这是一个特殊的图形，因此您提到的解决方案会容易得多（非桥边是循环中的边）。
我有一个无约束图 G=(V,E) 和权重函数 w:E->R+。另外，我有 G 的 MST T。
我必须构建一个执行以下操作的算法：
如果我们向 E 添加一个具有权重 w(e') 的新边 e'。建议一种更新 T 的算法，它将成为新图 G'=(V,EUe').
复杂度：O(V)。
我的建议是：
1) 将 e' 添加到 T。我们得到一个名为 T' 的新图，其中包含一个循环。
2) 运行 T' 上的 DFS 并标记您访问的每个顶点。另外保存
堆栈中的每个顶点和每个边缘权重。
3) 当我们访问一个我们已经访问过的顶点时，我们停止 运行.
4) 然后开始从堆栈中退出，直到我们到达我们停止的顶点。
5）在撤回时，我们保存从中撤回的最大边缘权重
堆叠.
6) 如果最大边缘权重大于 w(e') 我们替换它们。
7) 否则我们保持相同的 T。
我希望清楚。
如果有人能帮我解决问题，或者给我其他的，我将不胜感激
解决方案和建议。
是的，您建议的解决方案是正确的，因为具有相同数量的边和节点（如 T）的图由一个简单的循环组成，树根植于此的某些（可能 none）的节点循环.
您需要从 T 中恰好删除 1 条边，这样剩余的图仍然是连通的。显然最好的选择是删除最大的边。您可以在保持图形连接的同时删除的唯一边是循环中的边（您要添加到堆栈的边）。
另一种解决方案是在图中找到bridges，然后找到最大的非桥边并将其删除。但是，由于这是一个特殊的图形，因此您提到的解决方案会容易得多（非桥边是循环中的边）。