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) 更昂贵 -- 自相矛盾。

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