如何在从图中删除边后更新最小生成树？

Question

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

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

我已经成功处理了以下情况：

1.该边不存在； 2.该边在图中但不在MST中（MST不变）； 3.该边是两个节点之间唯一的路径（在这种情况下，我返回null，因为图不连通）。

当边在MST中且在图中形成了一个环时，我该怎么办？我需要在O(n+m)复杂度下完成此操作。

我用红色书写边的成本。

- Alin Ciocan

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之间会有两条或更多的边相互连接，而不仅仅是一条边。

换句话说，T1和T2分别是N1和N2上的最小生成树，e是它们之间代价最小的连接，否则( (T1和T2分别是N1和N2上的最小生成树) 且 (e是它们之间代价最小的连接) )将会为假。但是，任何连接T1和T2的路径都比e=(u,v)更加昂贵，这与之前的条件相矛盾。

省略了一些证明细节，希望能对你有所帮助。

- ashley

---

谢谢。知道这两棵树只需要通过一条边重新连接，MST 就能保持不变，对我非常有帮助。首先，我在 MST 中搜索 T1 和 T2（可以在 O(n) 的时间内完成），然后寻找连接 T1 和 T2 的边，并选择成本最低的边 - O(n+m)。 - Alin Ciocan

Ashley，你描述的算法是O(n^3)。“拿其中一个——比如说T2”。这需要O(n)的时间来找到T1和T2。“与T2上的节点相连的每条边要么在T2上，要么连接T2和T1。”将T1和T2连接的边数在最坏情况下为O(n^2)。确定它是否连接T1和T2需要O(n)的时间（搜索两个列表以匹配集合T1和集合T2中的一个）。因此，获取连接T1和T2的边的列表需要O(n^3)的时间。 - Michael Dotson

我认为这是 O(E) 的。在寻找原始MST时，将边缘与MST中的属性标记为：e.mst = 1 或 0。删除MST边缘后，沿着从每个顶点开始的MST向外搜索，将每个顶点标记为拆分MST的“左半部分”或“右半部分”的一部分。每一侧需要 O(E)。然后，对于所有边缘 (u, v)，如果 u 和 v 属于不同的MST半部分，则保留最小的这样的边缘并将其添加到MST中。 - brittohalloran