如何在 O(|E|) 中从图中删除一条边后更正 MST？
How to correct MST after deleting an edge from the graph in O(|E|)?
我是学算法的，看到一个习题是这样说的：
Let G=(V,E) be a weighted undirected graph. Let T be a MST for G. Let
e be an edge in T and let G'=(V,E') be the graph which obtained from
G after deleting e (i.e. E'=E/{e} ). G' is a connected graph. Describe
an algorithm that corrects T such that we will get a MST T' for G' in
O(|E|).
A 我明白，随着边的移除，T 现在被分成两个连接的组件 T1 和 T2，我们需要找到连接它们的最小距离路径，这是一条边，即我们需要找到连接 T1 和 T2 的最小权重边。
问题是我不知道如何证明这个算法以及如何在 O(|E|) 中实现它。我找到了 this solution 但它需要的时间超过 O(|E|).
我将不胜感激。
注意 |E| >= |V|.
选择任何顶点，将其标记为 component1，迭代每个连接的顶点（沿着 MST 边）并标记为 component1。那是 O(|V|).
通过扫描从另一个组件中找到一个顶点，直到没有标记为止。又是O(|V|)。
迭代第二个组件中的每个顶点（沿着 MST 边），选择连接到 component1 的非 MST 边。跟踪最小边缘答案。那是 O(|E|)
复杂度 O(|E|)
我是学算法的，看到一个习题是这样说的：
Let G=(V,E) be a weighted undirected graph. Let T be a MST for G. Let e be an edge in T and let G'=(V,E') be the graph which obtained from G after deleting e (i.e. E'=E/{e} ). G' is a connected graph. Describe an algorithm that corrects T such that we will get a MST T' for G' in O(|E|).
A 我明白，随着边的移除，T 现在被分成两个连接的组件 T1 和 T2，我们需要找到连接它们的最小距离路径，这是一条边，即我们需要找到连接 T1 和 T2 的最小权重边。
问题是我不知道如何证明这个算法以及如何在 O(|E|) 中实现它。我找到了 this solution 但它需要的时间超过 O(|E|).
我将不胜感激。
注意 |E| >= |V|.
选择任何顶点，将其标记为 component1，迭代每个连接的顶点（沿着 MST 边）并标记为 component1。那是 O(|V|).
通过扫描从另一个组件中找到一个顶点，直到没有标记为止。又是O(|V|)。
迭代第二个组件中的每个顶点（沿着 MST 边），选择连接到 component1 的非 MST 边。跟踪最小边缘答案。那是 O(|E|)
复杂度 O(|E|)