1

消費税はこちら

与えられたグラフ G (n 個の頂点と m 個の辺を持つ) の最小全域木 T と、G に追加する重み w の新しい辺 e = (u, v) が与えられたとします。グラフ G + e の最小全域木。完全なクレジットを受け取るには、アルゴリズムを 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.

トリッキーな部分は、O(n) 時間でこれを行う方法です。

問題は、MST の保存方法です。通常の Prim のアルゴリズムでは、MST は親配列として格納されます。つまり、各要素は対応する頂点の親です。

物品税が MST を示す親配列を私に与えると仮定すると、どうすれば上記のアルゴリズムを O(n) で解放できますか?

まず、親配列から u と v の間のパスを特定するにはどうすればよいですか? u と v の 2 つの祖先配列を使用して、共通の祖先をチェックすると、パスを取得できますが、逆になります。この部分で、共通の祖先を見つけるには、少なくとも O(n^2) で行う必要があると思いますよね?

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

...

したがって、O（n）でアルゴリズムを実行できるとは思いません。私が間違っている？

4

2 に答える 2

1

あなたの考えは正しいです。uとvの間のパスを見つけることに注意してくださいO(n)。parent arrayMST の識別情報があると仮定します。utovまたはutoからのパス (最大エッジの場合) を追跡するにroot vertexは、 のみを使用する必要がありO(n)ます。に到達した場合は、からまたはへroot vertexの道をたどってください。vuroot vertex

からのパスが得られたu -> u1 ... -> max_path_vert1 -> max_path_vert2 -> ... -> vので、エッジを削除しmax_path_vert1->max_path_vert2(これが追加されたエッジよりも大きいと仮定します)、 の親を逆にしてu->...->max_path_vert1をマークしparent[u] = vます。

編集：明確にするためのより多くの説明

MST では、頂点のペア間にパスが 1 つだけ存在することに注意してください。したがって、u->yとからトレースできる場合は、ほとんどの頂点v->yをトレースしただけです。n複数のn頂点をトレースした場合は、頂点を 2 回訪れたことを意味しますが、これは MST では発生しません。u->yでは、とから追跡するのは O(n) であると確信できたと思いますv->y。これらのパスを取得したら、 からのパスを確立したことになりますu->v。わかりますか？有向グラフの MST を見つけること自体が別の概念であるため、これは無向グラフであると想定しています。無向グラフの場合、 からのパスがあるx->y場合、 からのパスがありますy-x。だから、u->y->v存在します。y->vの重みは の重みv->yと同じになるため、 から遡る必要さえありません。y->v. u->yとからたどって重みが最大になるエッジを見つけるだけですv->y。

次に、O(1) でエッジの重みを見つけます。現在の体重をどのように保存していますか？隣接リストまたは隣接行列? O(1) アクセスの場合は、親の頂点配列が格納される方法で格納します。だから、weight[v] = weight(v, parent[v])。したがって、O(1) アクセスが可能になります。お役に立てれば。

于 2012-05-01T22:12:11.440 に答える
0

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

しかし、実装に関しては、T の代わりに G を使用して u と v の間のパスを見つける理由がわかりません。u と v の間のパスに T で検索トラバーサルを使用すると、O(n) が得られます。- つまり、v がルートであり、深さ優先検索アルゴリズムを実行すると仮定できます [この場合、v のすべての近隣を子として仮定する必要があります] - u を見つけたら DFS を停止します。スタック内のノードは、u と v の間のパスに対応します。

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

それはどういうわけか助けますか？

または、私の理解によると、O(n^2) を取得している可能性があります。これは、O(n) の T の頂点 v の子にアクセスするためです。ここでは、データ構造をマップされた配列として提示する必要があります。コストは O(1) に削減されます。[たとえば、{a,b,c,u,w}(頂点) -> {0,1,2,3,4}(頂点のインデックス)。

于 2012-05-01T22:15:49.350 に答える