对于以下问题,我有一个可能的解决方案,但不确定是否正确:
假设我们已经找到了加权无向图T的最小生成树G = (V,E)。如果T稍有改动,我们希望能够有效地更新G。
在G中添加一个边以生成一个新的图。给出了一种使用T在O(|V|)时间内为新图寻找最小生成树的算法。
我的算法:
for each vertex do
if smallest edge not in T then
replace this edge with existing edge in T
break
end if
end for
我没有多少写伪码的经验,所以我的算法可能过于简化或不正确。如果