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

Question

我在大学里遇到了以下问题:

让G =(V,E)为(无向)图与成本Ç _Ë上边缘> = 0 Ë ∈ Ë.假设给你一个最低成本生成树牛逼的摹.现在假设一个新的边缘被添加到ģ,连接两个节点v,吨_v ∈ V与成本Ç.

1. 提供一种有效的算法来测试T是否仍然是最小成本生成树,并将新边添加到G(但不添加到树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

Answer 1

你有正确的想法,但如果你以正确的方式存储树,你可以做比BFS更好的最短路径搜索.

说一个节点- [R在Ť是根(你可以选择从那里的任何节点和BFS以产生这样的结构,如果您已标记为矩阵或邻接列表的图形结构的树边缘),并且每个其它节点具有父指针和深度计数.为了找到之间的最短路径一和b在牛逼:

1. 让a成为'更深'的节点; 如果需要,交换.
2. 横动从父链接一个直到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有效地执行此操作也是读者的练习.

Answer 2

我相信你的步骤Find in T the shortest path from a to b是顺序E操作。