小编Lyn*_*tte的帖子

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

让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 …