给出一个无向图G= (V,E)。首先,人们问到MST的成本是多少。我可以很容易地使用Kruskall算法找到答案,如下所示:
G = (V, E)
for each edge (u, v) in E sorted by wight
{
if(Find(u) != Find(v))
{
Add (u, v) to the MST
Union(u, v); // put u and v in the same set
}
}
然后,对于初始图中的每一条边,询问新的MST的成本是多少--该边将出现在最小生成树中。
如果边缘已经存在于MST中,则