グラフ - ここ

Question

新しいエッジを追加した後の最小スパニングツリーを更新する実装は切除

我々が与えられたグラフ（n個の頂点とm個のエッジを有する）G の最小スパニングツリーTを与えられていると仮定していますGに追加するウェイトw の新しいエッジe =（u、v）を計算します。グラフG + eの最小 スパニングツリーを見つける効率的なアルゴリズムを与えます。 あなたのアルゴリズムはO（n） 時間で実行し、フルクレジットを受け取るようにしてください。

私はこのアイデアがありますトリッキーな部分はO（n）の時間でこれを行う方法であり、それは私が動けなくもあり

In the MST, just find out the path between u and v. Then find the edge (along the path) with maximum weight; if the maximum weight is bigger than w, then remove that edge from the MST and add the new edge to the MST.

---

を。

質問は、MSTがどのように格納されるかです。通常のプリムのアルゴリズムでは、MSTは親配列として格納され、すなわち、各要素は、対応する頂点の親である。

私がMSTを示す親配列を与えた場合、上記のアルゴリズムをO（n）でどのように公開することができますか？

まず、親配列からuとvの間のパスを特定するにはどうすればよいですか？私はuとvの2つの祖先配列を持つことができます。そして共通の祖先をチェックしてください。私はこの部分について、共通の祖先を見つけるために、少なくとも私はO（n^2）でそれをしなければならないと思います、そうですか？

次に、パスがあります。しかし、パスに沿って各エッジの重みを見つける必要があります。グラフはPrimのアルゴリズムにadjacency-listを使用すると仮定しているので、エッジの各重みを見つけるためにO（m）（mはエッジの数）を行わなければなりません。

...

だから私はO（n）の中でアルゴリズムを行うことが可能です表示されません。私が間違っている？

Answer 1

あなたの考えは正しいです。 uとvの間のパスを見つけることはO(n)であることに注意してください。 MSTを特定するparent arrayがあると仮定します。 uからvまたはuからroot vertexへのパスを追跡するには、O(n)を使用する必要があります。 root vertexに達した場合は、vからuまたはroot vertexに移動してください。

今、あなたはu -> u1 ... -> max_path_vert1 -> max_path_vert2 -> ... -> vからのパスを持っていることを、エッジmax_path_vert1->max_path_vert2（これは追加のエッジよりも大きいと仮定）を削除し、u->...->max_path_vert1とマークparent[u] = vために両親を逆転。

編集：MSTに頂点の任意のペアの間に正確に一つのパスが存在します、

注意わかりやすくするために詳細な説明。したがって、u->yとv->yからトレースすることができれば、極端にn個の頂点をトレースしただけです。 n個の頂点をトレースした場合は、頂点を2回訪問したことを意味します。これはMSTでは発生しません。さて、うまくいけば、u->yとv->yから追跡することがO（n）であると確信しています。これらのパスを取得したら、u->vからパスを確立しています。どうやって見える？有向グラフのMSTを見つけること自体は異なる概念なので、これは無向グラフであると仮定しています。無向グラフの場合、x->yからのパスを持つ場合、パスはy-xです。したがって、u->y->vが存在します。 からの追跡は、v->yの重みがy->vの重みと同じになるため、トレースする必要はありません。 u->yとv->yからトレースすると、最大の重みでエッジを見つけるだけです。

ここで、O（1）でエッジウェイトを検出します。現在の体重はどうやって保管していますか？隣接リストまたは隣接行列O（1）アクセスの場合、親頂点配列の格納方法を格納します。だから、weight[v] = weight(v, parent[v])。だから、あなたはO（1）のアクセス権を持っています。お役に立てれば。

Answer 2

あなたの解決策は正しいです。

しかし、私はなぜあなたはTの代わりにGを使ってuとvの間のパスを見つけられないのか分かりません.T内の任意の検索トラバーサルを使ってuとvの間のパスをO（n）にします。 - つまり、vがルートであり、深さ優先探索アルゴリズムを実行すると仮定することができます（この場合、vのすべての近傍を子供として仮定しなければなりません）。スタック内のノードはuとvの間のパスに対応します

パス内の各エッジのコスト（O（n））を見つけるのは簡単ですし、エッジを削除/追加することも簡単です。合計でO（n）。

これは何とか役立ちますか？

O（n^2）のTの頂点vの子にアクセスするため、私の理解によれば、O（n^2）を得ているかもしれません - ここでは、データ構造をコストがO（1）に減少するようにマップされた配列を使用します。 [instace、{a、b、c、u、w}（頂点） - > {0,1,2,3,4}（頂点のインデックス）。