Tarjan アルゴリズムと Kosaraju アルゴリズムの比較

Tarjan のアルゴリズムは、有向グラフ内の強くリンクされたコンポーネントを見つけるために 1972 年に Robert Tarjan によって作成された Tarjan のアルゴリズムと呼ばれるグラフ走査手法です。以前に処理されたノードを走査する代わりに、深さ優先検索戦略とスタック データ構造を使用して、関連性の高い各コンポーネントを効率的に見つけて処理します。このアルゴリズムはコンピューター サイエンスやグラフ理論で頻繁に使用され、アルゴリズムの作成、ネットワーク分析、データ マイニングなど、さまざまな用途に使用されます。

Kosaraju のアルゴリズムは、グラフの 2 つの走査で構成されます。最初のパスでは、グラフが逆の順序で走査され、各ノードに「完了時間」が割り当てられます。 2 番目のパスでは、完了時間の順にノードが訪問され、強く接続された各コンポーネントが識別されてラベルが付けられます。

Tarjan アルゴリズムの方法

この例では、Graph クラスがプログラムの先頭で定義され、そのコンストラクターがグラフ内の頂点の数に基づいて隣接リスト配列を初期化します。 addEdge 関数は、ソース頂点の隣接リストにターゲット頂点を含めることによって、グラフにエッジを追加します。

SCCUtil メソッドは、SCC を検出するために SCC メソッドによって使用される DFS ベースの再帰関数であり、このプログラムの基礎を形成します。現在の頂点 u、検出回数の配列 disc、低い値の配列 low、頂点スタック st の配列、およびスタック上に頂点があるかどうかを追跡するブール値の配列 stackMember、はこの関数への入力です。

このプロシージャは、現在の頂点をスタックに置き、最初に検出時間と低い値を割り当てた後、その stackMember 値を true に変更します。その後、近隣のすべての頂点の低い値を現在の頂点に再帰的に更新します。

この手法では、未発見の頂点 vs を繰り返し訪問し、u の低い値を変更します。 v がすでにスタック上にある場合、このメソッドは v が検出された時刻に基づいて u の下限値を変更します。

Tarjan アルゴリズム

• 初期化アルゴリズム

• チャートの移動を開始

• 強力な接続コンポーネントを確認する

• すべてのノードにアクセスするまで繰り返します

• 強結合コンポーネントを返す

このメソッドは、現在の頂点 u がポップされるまでスタックからすべての頂点をポップし、ポップされた頂点を出力し、u がヘッド ノードの場合 (つまり、その低い値が検出時間と等しい場合)、その stackMember を設定します。値を false に設定します。

＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー

方法 2-コサラジュ

コサラジュアルゴリズム

訪問したノードのコレクションと起動時に空のスタックを作成します。

• まだ訪問されていないグラフ内の最初のノードから深さ優先検索を開始します。検索中に訪問した各ノードをスタックにプッシュします。

• 各グラフィックのエッジの方向は反転する必要があります。

• スタックがまだノードでいっぱいの場合は、スタックからノードをポップします。 ノードが訪問されていない場合は、そのノードから深さ優先検索が実行されます。検索中に訪問した各ノードを、現在の高度にリンクされたコンポーネントのメンバーとしてマークします。

• すべてのノードにアクセスするまで繰り返します

。

• 高度に相互接続された各コンポーネントが識別され、プログラムの最後に注釈が付けられます。

• 次の C コードは、Kosaraju のアルゴリズムを使用して、有向グラフ内の強連結成分 (SCC) を見つけます。ソフトウェアは、次のメンバー関数を持つ Graph という名前のクラスを定義します。

  Graph(int V): コンストラクター。頂点 V の数を入力し、グラフの隣接リストを初期化します。

Void addEdge(int v, int w): このメソッドは、2 つの整数 v と w を入力として使用して、グラフ内の頂点 v と頂点 w を接続するエッジを作成します。

void printSCCs() 関数は、Kosaraju アルゴリズムを使用してグラフ内の各 SCC を出力します。

Graph getTranspose() メソッドは、グラフの転置を提供します。

再帰関数 void fillOrder(int v, bool Visited[, stack& Stack], int v) を使用して、完了時刻の順に頂点をスタックに追加します。

例 2

リーリー ＃＃＃出力＃＃＃ リーリー ＃＃＃結論は＃＃＃

要約すると、Tarjan と Kosaraju の方法の時間計算量は O(V E) です。ここで、V はグラフ内の頂点のセットを表し、E はグラフ内のエッジのセットを表します。 Tarjan のアルゴリズムの定数係数は、Kosaraju の方法の定数係数よりも大幅に低くなります。 Kosaraju の方法はグラフを少なくとも 2 回横断するため、定数係数はおそらく 2 倍になります。 2 番目の DFS が完了すると、Kosaraju のメソッドを使用して現在アクティブな SCC を生成できます。 SCC サブツリーの先頭が見つかると、Tarjan アルゴリズムを使用して SCC を出力するのに時間がかかります。

2 つの方法の線形時間計算量は同じですが、SCC 計算に使用される方法またはプロセスにはいくつかの違いがあります。 Kosaraju の手法はグラフ上で 2 つの DFS (または、元のグラフを変更しないままにしたい場合は 3 つの DFS) を実行し、グラフのトポロジカルな順序を決定する方法と非常によく似ていますが、Tarjan の手法はノード レコードのみに依存し、DFS がグラフを分割します。 。

以上がTarjan アルゴリズムと Kosaraju アルゴリズムの比較の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。