解体のためのグラフアルゴリズム

Question

グラフにはn個の頂点とm個のエッジがあります。グラフが接続を開始し、リストに表示されている順にエッジが削除されます。プロセスが終了すると、グラフは切断されます。

したがって、削除する前にn/4個の頂点の床よりも1つ多い接続されたコンポーネントがあるように、エッジのリストに特定のエッジがあります。このエッジを除去した後、n/4個の頂点の床よりも大きいグラフには、連結成分はありません。

どのように私はこのエッジを見つけるための最良のアルゴリズムを工夫するつもりです。エッジを削除してグラフをたどって、接続されている最大のコンポーネントで十分かどうかをチェックしますか？それはO（nm）の時間で実行されますが、私はいくつかのより速い方法が必要であるように感じる。答えは、接続されたコンポーネントを見つけるために分解されたセットを使用することと関係があると思いますが、実装する方法についてはわかりません。

Answer 1

を逆にして実行することを検討してください。エッジを削除するのではなくエッジを追加してください。このプロセスはKruskalのアルゴリズムと非常に似ています（すべてのノードは単独で始まり、接続されている別のコンポーネントにエッジが追加されます）。ただし、少なくとも1つの接続されたコンポーネントが少なくともn/4＆rfloor ;その中のノード。

これを解決する1つの方法は、Kruskalのアルゴリズムの改訂バージョンと、union-find構造の各代表が接続されたコンポーネントにノードの数を格納するように拡張されたunion-findデータ構造を使用することです。端点がすでに接続されている場合はエッジを破棄し、そうでない場合はリンクします。少なくとも＆lf; n/4＆rf;の接続されたコンポーネントが存在するエッジを追加すると、あなたが探しているエッジを見つけました。これは、実際には本質的に直線的なunion-findデータ構造の高速実装を使用すると、時間O（n + m α（n））で実行されます。