コサラジュのアルゴリズム

コンピュータサイエンスにおいて、コサラジュ・シャリルのアルゴリズム（コサラジュのアルゴリズムとも呼ばれる）は、有向グラフの強連結成分を見つける線形時間 アルゴリズムである。Aho 、Hopcroft、Ullmanは、このアルゴリズムをS. Rao KosarajuとMicha Sharirに帰属させている。コサラジュは1978年にこのアルゴリズムを提案したが公表しなかったが、シャリルは独自にこのアルゴリズムを発見し、1981年に公表した。このアルゴリズムは、転置グラフ（すべての辺の方向が逆になった同じグラフ）が元のグラフとまったく同じ強連結成分を持つという事実を利用している。

アルゴリズムが使用する基本的なグラフ操作は、グラフの頂点を列挙すること、頂点ごとにデータを格納すること (グラフ データ構造自体に格納されていない場合は、頂点をインデックスとして使用できるテーブルに格納)、頂点の外隣接を列挙すること (順方向にエッジをトラバース)、および頂点の内隣接を列挙すること (逆方向にエッジをトラバース) です。ただし、最後の操作は、順方向トラバース フェーズ中に転置グラフの表現を構築するという代償を払えば、実行しなくてもかまいません。アルゴリズムに必要な唯一の追加データ構造は、グラフの頂点の順序付きリストLであり、これは各頂点を 1 回ずつ含むように大きくなります。

強い成分を、各成分に別々のルート頂点を指定し、各頂点にその成分のルート頂点を割り当てることによって表現する場合、Kosaraju のアルゴリズムは次のように記述できます。

1. グラフの各頂点uを未訪問としてマークします。Lを空にします。
2. グラフの各頂点uに対してVisit(u)、Visit(u)再帰サブルーチンを実行します。

   uが未訪問の場合:

   1. 訪問済みとしてマークします。
   2. uの各外隣接点vに対して、 を実行します。Visit(v)
   3. Lの前にu を追加します。

   それ以外の場合は何もしません。

3. Lの各要素uに対して、再帰サブルーチンを 実行する。Assign(u,u)Assign(u,root)

   u がコンポーネントに割り当てられていない 場合は、次のようになります。

   1. u を、ルートがrootであるコンポーネントに属するものとして割り当てます。
   2. uの各同近傍vに対して、 を実行します。Assign(v,root)

   それ以外の場合は何もしません。

簡単なバリエーションとしては、各頂点にコンポーネント番号を割り当てるか、それに属する頂点のコンポーネントごとのリストを作成することです。未訪問/訪問済みの表示は、頂点のルートの最終的な割り当てと保存場所を共有する場合があります。

このアルゴリズムの重要な点は、グラフ エッジの最初の (順方向の) トラバース中に、探索中の検索ツリーに対して後順で頂点がリストLの先頭に追加されることです。つまり、頂点vが最初に訪問されたのは、すべての頂点の列挙に表示されたためか、訪問された別の頂点uの外隣接頂点であったためかは関係ありません。いずれにしても、 v はuより前にLの先頭に追加されるため、 uからvへの順方向パスがある場合、最終的なリストLではuがvより前に表示されます( uとv の両方が同じ強いコンポーネントに属している場合を除きます。この場合、Lでの相対的な順序は任意です)。

これは、リストの各要素n をブロックL[ i _{n -1} : i _n ]に対応させることができることを意味します。ここで、ブロックは、パス内の各ノードで外向きのエッジのみを使用して頂点nから到達可能なすべての頂点で構成されます。 nで始まるブロック内のどの頂点も、その右側の頂点で始まるブロック、つまり、リスト内の頂点i _n、i _{n +1}、… Nに対応するブロックのいずれからも内向きリンクを持たないことに注意することが重要です。これは、そうでなければ、内向きリンクを持つ頂点 (たとえば、 n' ≥ i _{n +1}で始まるブロックから) が既に訪問され、 n'のブロック内のLの前に追加されているため、矛盾が生じるためです。一方、nで始まるブロック内の頂点は、 { i _n、i _{n +1}、… N }内のいずれかの頂点で始まるブロックを指すエッジを持つことができます。

アルゴリズムのステップ 3 は、L[0]から始まり、それを指すすべての頂点にL[0]と同じコンポーネントを割り当てます。これらの頂点はL[0]で始まるブロック内にのみ存在できることに注意してください。これは、上位のブロックはL[0]のブロック内の頂点を指すリンクを持つことができないためです。 L[0]を指すすべての頂点の集合をIn(L[0])とします。続いて、これらの頂点を指すすべての頂点In(In(L[0]))も追加され、頂点を追加できなくなるまでこれが続きます。

L[ 0 ]を含むコンポーネントに追加されたすべての頂点から、 L [0 ]へのパスが存在します。また、 L[0] から追加されたすべての頂点へのパスも存在します。これは、それらすべてがL[0]で始まるブロック内にあるためです(このブロックには、パスの各ステップで外向きのエッジをたどってL[0]から到達可能なすべての頂点が含まれます)。したがって、これらすべてが 1 つの強く接続されたコンポーネントを形成します。さらに、頂点は残りません。これは、この強く接続されたコンポーネント内にあるためには、頂点はL[ 0] から到達可能であり、 L[0]に到達可能でなければならないためです。L[0]に到達可能なすべての頂点 (もしある場合) は最初のブロックのみにあり、最初のブロック内のすべての頂点はL[0]から到達可能です。したがって、アルゴリズムはL[0]の接続されたコンポーネント内のすべての頂点を選択します。

ステップ 3 のループで頂点v = L[ i ]に到達し、v がどのコンポーネントにも割り当てられていない場合、左側のすべての頂点が接続コンポーネントを作成したことがわかります。つまり、v はどのコンポーネントにも属しておらず、v は左側のどの頂点も指していないということです。また、上位のブロックからvのブロックへの辺は存在しないため、証明は同じままです。

上で示したように、アルゴリズムは単純化のために深さ優先探索を採用していますが、後順序プロパティが保持される限り、 幅優先探索を使用することもできます。

このアルゴリズムは、頂点uの強い成分を、uから後方および前方の両方の走査で到達可能な頂点の集合として識別するものとして理解できます。uから前方走査で到達可能な頂点の集合をF ( u )、uから後方走査で到達可能な頂点の集合をB ( u )、アルゴリズムのフェーズ 2 の後のリストLでuより厳密に前に現れる頂点の集合をP ( u )と記述すると、ルートとして指定された 頂点u を含む強い成分は次のようになります。

${\displaystyle B(u)\cap F(u)=B(u)\setminus (B(u)\setminus F(u))=B(u)\setminus P(u).}$

集合の交差は計算コストがかかりますが、論理的には二重集合の差と同等であり、B ( u )の新たに${\displaystyle B(u)\setminus F(u)\subseteq P(u)}$遭遇した要素がすでにコンポーネントに割り当てられているかどうかを テストするだけで十分になります。

グラフが隣接リストを使用して記述されている場合、Kosaraju のアルゴリズムはグラフの完全な走査を 2 回実行するため、Θ(V+E) (線形) 時間で実行されます。これは、一致する下限値があるため漸近的に最適です (どのアルゴリズムでもすべての頂点と辺を調べる必要があります)。これは概念的には最も単純で効率的なアルゴリズムですが、実際にはグラフの走査を 1 回しか実行しないTarjan の強連結成分アルゴリズムやパスベースの強成分アルゴリズムほど効率的ではありません。

グラフが隣接行列として表現される場合、アルゴリズムにはΟ(V ² )時間が必要です。

• Alfred V. Aho、John E. Hopcroft、Jeffrey D. Ullman著『データ構造とアルゴリズム』Addison-Wesley、1983 年。
• Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein。アルゴリズム入門、第3版。MIT Press、2009年。ISBN  0-262-03384-4。
• ミカ・シャリル. 強連結アルゴリズムとデータフロー解析への応用. コンピュータと数学の応用7(1):67–72, 1981.

• 良い数学、悪い数学: 強く連結したコンポーネントの計算