"Unionとfind"の逆の操作

互いに独立したセットの "Union and find"があります。 http://en.wikipedia.org/wiki/Union_find "Unionとfind"の逆の操作

しかし、逆の操作はどうしますか？ N個のノードがEエッジ（実際にはグラフ）に接続されたセットを考えてみましょう。そして、各ステップでいくつかのエッジを削除し、この削除操作が別のセットを持っていないかどうかをチェックします。それは "連合と見つける"のように速くそれをすることは可能ですか？これは宿題ではありません

P.Sは、私たちは休日を持っている:)

出典

2011-06-22 Spinach

これは、オンラインエッジ削除問題やオンライン接続の問題として知られています。アルゴリズムへのリンクはsection of the Wikipedia article on graph connectivityにあります。

出典

2011-06-22 10:24:52

リンクありがとうございます。私はACMで購入する記事しか見つけることができません。私たちは、各段階でブリッジを検出することがより効率的になることができます。これは、TopCoderのすべての情報を見つけることができませんでした： – Spinach

Bridgeを効率的に検出するにはどうすればよいですか？これは線形時間で行うことができます（リンクも参照）。

出典

2011-06-22 10:25:43 dcn

@Chrisは明らかに操作を繰り返したいと思っています。 – borrible

私はあなたがそのブリッジを見つけるアルゴリズムを実行し、ブリッジをマークし、エッジがグラフに追加されない限り、新しいブリッジは現れないことに注意してください。そのグラフに存在するすべてのブリッジは、エッジが削除されてもブリッジとして残り、新しいブリッジは、ブリッジではないエッジを削除した場合にのみ表示されます。したがって、削除されたブリッジ以外のエッジで接続された2つのサブグラフでアルゴリズムを再実行するだけで済みます。 –

Union-findは、サイクルを作成しない最小ウェイトのエッジを繰り返し追加するKruskalアルゴリズムで使用されます。逆の考え方 - グラフを切り離さない限り最大の重みのエッジを取り除く - は、reverse-delete algorithmで使用されています。これはいくつかの複雑なデータ構造を使用するように見えます（Wikipedia参照）。

出典

2011-06-22 11:29:03 sdcvvc

次の素晴らしいリンクですが、あまりにも一般化され、本当に見るコードはありません:( – Spinach

答えて

関連する問題