algorithm - 从图中删除边后如何更新 MST？

Question

我有一个用邻接列表表示的图，他的 MST 用父数组表示。

我的问题是我需要从图中删除一条边并更新父数组。

我已经设法处理以下情况：

1. 边缘不存在；
2. 边缘在图中但不在 MST 中（MST 不变）；
3. 并且边缘是来自两个节点的唯一路径（在这种情况下，我返回 null，因为图未连接）。

当边缘在 MST 中并且图中的边缘处于循环中时，我该怎么办？我需要在O(n+m) 复杂性中做到这一点。

我用红色写边的成本。

Answer 1

只需搜索现在断开连接的树部分到树的其余部分的最小距离路径，然后在中间添加该路径——这是一条边。

假设你的原始树是 T。随着边缘的移除，它现在被分成树 T1 和 T2。

拿其中一个——比如说T2。与 T2 上的节点相连的每条边要么在 T2 上，要么是连接 T2 和 T1 的边。在这些与 T2 上的一个节点相关的边中，选择一个 ( (其另一端位于 T1 节点) 和 (在所有此类边中具有最小成本) )。搜索这条边，比如 e=(u,v)，需要 O(|E|) 时间。O(|N|) 如果分离的部分是叶子。

如果有一棵树，比如 T'，其成本低于 T1 \union T2 \union {e}，那么 T1 和 T2 的节点集 N1 和 N2 将具有比仅一条边更多的互连，

即，T' 上有两条或更多条边，它们从 N1 中的一个节点开始，到 N2 中的一个节点结束。否则，（（T1 和 T2 是最小生成树响应。超过 N1 和 N2）和（e 是 T1 和 T2 之间成本最低的连接））将是错误的。但是，T1 和 T2 之间的任何中间人都比 e=(u,v) 更昂贵——这是矛盾的。

跳过了一些证明细节。希望这可以帮助。