插入新边时更新最小生成树

Question

我在大学中遇到了以下问题：

假设G =（V，E）是带有边缘e∈E的成本c_e>=0的（无向）图。假设您已在G中给出了最小成本生成树T。现在假设向G添加了一个新的边缘，将两个节点v，t_v∈V与成本c连接。

1. 提供一种有效的算法来测试在向G添加新边缘（但不是树T）时是否保留最小成本生成树T。使您的算法以O（| E |）的时间运行。您能否在O（| V |）时间内完成？请注意，您对用于表示树T和图形G的数据结构做出的任何假设。
2. 假设T不再是最小成本生成树。给出一个线性时间算法（时间O（| E |））来更新树T为新的最小成本生成树。

这是我找到的解决方案：

Let e1=(a,b) the new edge added
Find in T the shortest path from a to b (BFS)
if e1 is the most expensive edge in the cycle then T remains the MST
else T is not the MST

看起来它可以工作，但我很容易让它在O（|V|）时间内运行，而问题要求O（|E|）时间。我错过了什么吗？

顺便说一下，我们被授权向任何人寻求帮助，所以我不是在作弊:D

- Lynette

---

也许我漏掉了什么——毕竟 G 是连通图，所以 |V| <= |E| + 1 吧？因此，你的 O(|V|) 算法自动也是 O(|E|)，那么问题出在哪里呢？还是说你在说：“我惊讶地发现我能够比问题所要求的解决得更好”？ - j_random_hacker

是的，就像那样！我很惊讶在O（|V|）中做起来如此简单，但两个问题都要求它在O（|E|）中。我担心有些事情我没有看到。另外，我必须证明我的解决方案，很明显，如果e1是一个环上最昂贵的边，则它不能在MST中，如果e2比e1更昂贵，则e2不能在图中，但是通过e1的新路径的可能性不能创造一个包含在G中但不在先前MST T中的边的MST吗？ - Lynette

除非有人告诉你，否则我认为在一个环中没有最长边的属性并不是"显而易见"的。因此，我认为这个问题并不是“太简单了”。关于您的证明问题：假设存在包含e1的这样一个MST。那么删除e1会留下2个连通分量。因为e1最初是环的一部分，所以必须有一些其他边连接这两个连通分量（证明这一部分留作练习 :-P），并且具有权重<w(e1)。添加该边以产生一个较小的MST，从而产生矛盾。因此不存在包含e1的MST。 - j_random_hacker

我得出了与你 j_random_hacker 相同的证明，并且即使存在多个相同权重的边，我也认为这没有问题。让我困惑的是，我认为我可以证明在第二种情况下，你只需要添加新边并删除最重的边（如果有多个，则删除任意一个），仍然可以在 O（|V|）内运行。 - michalburger1

@Bus：现在我明白了！我的瓶颈在于删除最重边不是“安全”的（因为可能存在包含该边的MST），因为我们不能确定是否有更好的边可以连接这两个组件。但是，所有MST都需要的是对于任何顶点的二分图，我们选择跨越该二分图的最小权重边之一。因此，给定一个二分图和跨越它两次的循环，即使两个跨越边都是最重的，也可以选择其中任意一个 - 两者都将产生MST。因此，删除最重边将得到一个MST，但不一定是所有MST。 - j_random_hacker

Answer 1

你的想法是对的，但如果你以正确的方式存储树，就可以比BFS更好地进行最短路径搜索。

假设树T中有一个节点r是根节点（如果您已经在矩阵或邻接列表图结构中标记了树边，则可以从其中任何节点开始BFS以生成此结构），每个其他节点都有一个父指针和深度计数。要查找a和b之间的最短路径：

1. 让a成为“深”的节点；如果需要，交换它们。 2. 从a开始遍历父链接，直到达到b或r，同时存储遍历的路径，标记已访问的节点。 3. 如果到达b，则最短路径是所遍历的路径。 4. 如果到达r，则还要从b到根遍历；如果到达从a到r的遍历中到达的节点，则停止。将它们相遇的地方连接起来，这样就得到了T中的最短路径。

该算法的有效性证明留给读者作为练习。这与BFS一样是O（|V|），但通常会更快。实际上，只有少数MST配置需要O（|V|）时间。当然，生成父链接树需要O（|V|）时间，因此只有在某些情况下才有帮助，例如如果您使用自然在确定MST过程中创建此结构的MST构建算法。

正如另一位评论者所说，注意如果图形有MST，则它是连通的，因此|V| <= |E|，因此O（|V|）< O（|E|）。

此外，要在O（|V|）时间内修复树（如果需要），只需找到循环中最长的边并将其删除，用新边替换即可。使用父链接MST有效地执行此操作也是读者的练习。

- Walter Mundt

Answer 2

我认为BFS足以解决问题。它的复杂度是O（|V| + |E|），但在一棵树中，|E|小于|V|，因此它的复杂度是O（2|V|），即O（|V|）

- Mokuchan

Answer 3

我认为你的步骤 从a到b在T中找到最短路径 是一个O(E)操作。

- verisimilidude

---

不，T中有|V|-1条边。 - Charles Stewart