如何从图形中删除边后更新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）昂贵-这是矛盾的。

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