最小スパニング ツリー用の C++ の Boruvka アルゴリズム

グラフ理論では、接続された重み付きグラフの最小スパニング ツリー (MST) を見つけることが一般的な問題です。 MST は、すべての頂点を接続し、合計エッジの重みを最小化するグラフ エッジのサブセットです。この問題を解決する効率的なアルゴリズムが Boruvka アルゴリズムです。

次に、Boruvka アルゴリズムで最小スパニング ツリーを見つける手順の概要を説明します。 -

MST を空のセットに初期化します。

• 各頂点のサブセットを作成します。各サブセットには頂点が 1 つだけ含まれます。

• 最小スパニング ツリー (MST) に V-1 個のエッジができるまで次の手順を繰り返します (V はグラフ内の頂点の数です) −

• 各サブセットについて、他のサブセットに接続する最も安価なエッジを見つけます。

  • 選択したエッジを最小スパニング ツリーに追加します。

  • 選択したエッジのサブセットに対して結合操作を実行します。

  最小スパニングツリーを出力します。
• ＃＃＃方法＃＃＃

  Boruvka アルゴリズムでは、各サブセットを接続する最も安価なエッジを見つける方法が複数あります。以下に 2 つの一般的な方法を示します。 -

方法 1: 簡単な方法

各サブセットについて、すべてのエッジをトラバースし、それを別のサブセットに接続する最小のエッジを見つけます。

選択したエッジを追跡し、ジョイント操作を実行します。

説明

説明

最初に、エッジとサブセットという 2 つの構造を定義します。エッジは、エッジのソース、宛先、重みを含むグラフ内のエッジを表します。サブセットは、親およびランキング情報を含むユニオン クエリ データ構造のサブセットを表します。

find 関数は、パス圧縮を使用して要素のサブセットを検索するヘルパー関数です。要素が属するサブセットの代表 (親ノード) を再帰的に検索し、パスを圧縮して将来のクエリを最適化します。

unionSets 関数は、ランクベースのマージを使用して 2 つのサブセットをマージするもう 1 つの補助関数です。 2 つのサブセットの代表を見つけて、ランクに基づいてそれらをマージし、バランスの取れたツリーを維持します。

boruvkaMST 関数は、エッジ ベクトルと頂点の数 (V) を入力として受け取ります。 MST を見つけるために Boruvka アルゴリズムを実装します。

boruvkaMST 関数内で、MST のエッジを保存するベクトル selectedEdges を作成します。

サブセットを表す Subset 構造体の配列を作成し、デフォルト値で初期化します。

また、各サブセットの最も安価なエッジを追跡するために、最も安価な配列も作成します。

変数 numTrees は頂点の数に初期化され、MSTWeight は 0 に初期化されます。

アルゴリズムは、すべてのコンポーネントがツリー内に収まるまでコンポーネントを繰り返し結合することによって進められます。メイン ループは、numTrees が 1 になるまで実行されます。

メイン ループの各反復で、すべてのエッジを反復し、各サブセットの最小重み付きエッジを見つけます。エッジが 2 つの異なるサブセットを接続する場合、最も重みの低いエッジのインデックスで最も安価な配列を更新します。

Next, we traverse all subsets. サブセットに最小の重みを持つエッジがある場合、それを selectedEdges ベクトルに追加し、MSTWeight を更新し、サブセットの和集合演算を実行して、numTrees の値を減らします。

最後に、MST 重みと選択したエッジを出力します。

main 関数は、ユーザーに頂点とエッジの数を入力するよう求めます。次に、各エッジの入力 (ソース、ターゲット、重み) を取得し、その入力を使用して boruvkaMST 関数を呼び出します。

方法 2: 優先キューを使用する

重みでソートされた優先キューを作成してエッジを保存します。

各サブセットについて、優先キューから別のサブセットに接続する最小重みエッジを見つけます。

選択したエッジを追跡し、ジョイント操作を実行します。

説明

説明

このアプローチでは、優先キューを使用して、各サブセットの最小重み付きエッジを見つけるプロセスを最適化します。以下はコードの詳細な説明です-

コード構造とヘルパー関数 (find や UnionSets など) は、前のメソッドと同じままです。

boruvkaMST 関数は、優先キューを使用して各サブセットの最小加重エッジを効率的に見つけるように変更されました。

最も安価な配列を使用する代わりに、エッジ優先キュー (pq) を作成します。グラフの端で初期化します。

メイン ループは、前のメソッドと同様に、numTrees が 1 になるまで実行されます。

各反復で、優先キューから最小重みエッジ (minEdge) を抽出します。

次に、検索関数を使用して、minEdge のソースとターゲットが属するサブセットを検索します。

サブセットが異なる場合は、minEdge を selectedEdges ベクトルに追加し、MSTWeight を更新し、サブセットのマージを実行して、numTrees を減らします。

プロセスは、すべてのコンポーネントがツリー内に配置されるまで続行されます。

最後に、MST 重みと選択したエッジを出力します。

主な機能は前の方法と同じですが、テスト目的で事前定義された入力があります。

Boruvka のアルゴリズムは、重み付きグラフの最小スパニング ツリーを見つけるための効率的なソリューションを提供します。私たちのチームは、C でアルゴリズムを実装する際に、従来のアプローチまたは「単純な」アプローチという 2 つの異なるパスを詳しく調査しました。もう 1 つは優先キューを利用するものです。当面の問題の特定の要件によって異なります。各方法には特定の利点があり、それに応じて実装できます。 Boruvka のアルゴリズムを理解して実装することで、C プロジェクトの最小スパニング ツリー問題を効率的に解決できます。

以上が最小スパニング ツリー用の C++ の Boruvka アルゴリズムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。