グラフ理論では、接続された重み付きグラフの最小スパニング ツリー (MST) を見つけることが一般的な問題です。 MST は、すべての頂点を接続し、合計エッジの重みを最小化するグラフ エッジのサブセットです。この問題を解決する効率的なアルゴリズムが Boruvka アルゴリズムです。
###文法### リーリー ###アルゴリズム###MST を空のセットに初期化します。
各頂点のサブセットを作成します。各サブセットには頂点が 1 つだけ含まれます。
最小スパニング ツリー (MST) に V-1 個のエッジができるまで次の手順を繰り返します (V はグラフ内の頂点の数です) −
各サブセットについて、他のサブセットに接続する最も安価なエッジを見つけます。
選択したエッジを最小スパニング ツリーに追加します。
選択したエッジのサブセットに対して結合操作を実行します。
Boruvka アルゴリズムでは、各サブセットを接続する最も安価なエッジを見つける方法が複数あります。以下に 2 つの一般的な方法を示します。 -
選択したエッジを追跡し、ジョイント操作を実行します。
###例### リーリー ###出力### リーリー説明
最初に、エッジとサブセットという 2 つの構造を定義します。エッジは、エッジのソース、宛先、重みを含むグラフ内のエッジを表します。サブセットは、親およびランキング情報を含むユニオン クエリ データ構造のサブセットを表します。
サブセットを表す Subset 構造体の配列を作成し、デフォルト値で初期化します。
また、各サブセットの最も安価なエッジを追跡するために、最も安価な配列も作成します。
変数 numTrees は頂点の数に初期化され、MSTWeight は 0 に初期化されます。
アルゴリズムは、すべてのコンポーネントがツリー内に収まるまでコンポーネントを繰り返し結合することによって進められます。メイン ループは、numTrees が 1 になるまで実行されます。
メイン ループの各反復で、すべてのエッジを反復し、各サブセットの最小重み付きエッジを見つけます。エッジが 2 つの異なるサブセットを接続する場合、最も重みの低いエッジのインデックスで最も安価な配列を更新します。
Next, we traverse all subsets. サブセットに最小の重みを持つエッジがある場合、それを selectedEdges ベクトルに追加し、MSTWeight を更新し、サブセットの和集合演算を実行して、numTrees の値を減らします。
最後に、MST 重みと選択したエッジを出力します。
main 関数は、ユーザーに頂点とエッジの数を入力するよう求めます。次に、各エッジの入力 (ソース、ターゲット、重み) を取得し、その入力を使用して boruvkaMST 関数を呼び出します。
方法 2: 優先キューを使用する
重みでソートされた優先キューを作成してエッジを保存します。
各サブセットについて、優先キューから別のサブセットに接続する最小重みエッジを見つけます。
選択したエッジを追跡し、ジョイント操作を実行します。
###例### リーリー ###出力### リーリー説明
の中国語訳は次のとおりです:このアプローチでは、優先キューを使用して、各サブセットの最小重み付きエッジを見つけるプロセスを最適化します。以下はコードの詳細な説明です-
コード構造とヘルパー関数 (find や UnionSets など) は、前のメソッドと同じままです。
boruvkaMST 関数は、優先キューを使用して各サブセットの最小加重エッジを効率的に見つけるように変更されました。
サブセットが異なる場合は、minEdge を selectedEdges ベクトルに追加し、MSTWeight を更新し、サブセットのマージを実行して、numTrees を減らします。
プロセスは、すべてのコンポーネントがツリー内に配置されるまで続行されます。
最後に、MST 重みと選択したエッジを出力します。
主な機能は前の方法と同じですが、テスト目的で事前定義された入力があります。
###結論は###以上が最小スパニング ツリー用の C++ の Boruvka アルゴリズムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。