Kruskalのアルゴリズム：エッジが強制的になるときのMSTの更新

Question

無向グラフG =（V、E）が与えられます。最初に、MSTの費用は何か尋ねられます。 私は簡単にこのように、クラスカルのアルゴリズムを使用して見つけることができます。その後

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に存在する場合、回答は同じままです。それ以外の場合は、もう一度Kruskallを実行できます。擬似コードは以下の通りです：

G = (V, E) 
G1 = runKruskall(G) 

for each edge (u, v) in E 
{ 
    ClearUnionSets() 
    if (u, v) in G1 
    { 
     print costOf(G1) 
    } else { 
     Union(u, v) 
     G2 = runKruskall(G) 
     print costOf(G2) 
    } 
} 

そのアプローチの問題点は、総複雑であろうことである：O（E * E）

説明するようにMSTを更新するためのよりよい解決策が存在するならば私の質問です上記。

私が考えていたのは、Kruskallをすべてのエッジ（u、v）に対してuとvが同じ集合になったときに、既に部分MSTに存在する最大重み付けエッジを見つけ出すことです（u、v）でサイクルを作り、その情報をM [u] [v]の行列Mに格納する。これを行うと、エッジが必須になったときにMSTを更新する問題は、O（1）で解決されます。

誰もがこれを手伝ってくれますか？

Answer 1

MST上にないすべてのエッジu-vについて、エッジを含む最小のスパニングツリーは、MST上でu-vがパス上の最大のエッジをuからvに置き換えたものです。

置換するエッジは、以下のように効率的に見つけることができます。まず、任意の頂点でMSTをルートします。アルゴリズムを修正して、2つの頂点のlowest common ancestor（LCA）を見つけます（here）。各頂点に2番目の親を格納することに加えて、2番目の親へのパスにも最大の辺を格納します。この配列を使用して、LCAを計算する際に、LCAへのパス上の最大のエッジも計算します。これにより、2つの頂点間のパス上で最大のエッジが得られます。

前処理では、O（E log E）内のMSTを見つけ、O（N log N）空間にLCAの親テーブルを作成します。この後、各エッジの修正されたMSTを見つけることは、O（log N）で実行できるLCAの評価のみを必要とする。したがって、全体の複雑さはO（E log E）だけである。