強く連結されたコンポーネントを解決するための Tarjan アルゴリズムを実装する 20 行のコード

今日紹介するアルゴリズムは Tarjan と呼ばれていますが、これも非常に奇妙な名前です。奇妙なのは、これもまた人の名前にちなんで名付けられているからです。 Kosaraju アルゴリズムと比較すると、名前が覚えやすいことに加えて、再帰が 1 回だけ必要なことも利点です。アルゴリズムの複雑さは同じですが、定数は小さくなります。知名度も高く、競技会にも頻繁に登場します。

まず最初に、Tarjan アルゴリズムは Kosaraju アルゴリズムよりも理解するのが難しいということを思い出してください。ですので、この記事を読んでも理解できない場合は、前回の記事を読むことをお勧めします。これら 2 つのアルゴリズムの効果と複雑さは同じです。実際、学習する必要があるのは 1 つだけで、それに固執する必要はありません。

アルゴリズムフレームワーク

質問について考えてみましょう。強連結成分分解アルゴリズムの核となる原理は何でしょうか?

弊社の以前の記事を読んでいただければ、この質問に答えるのは難しくないはずです。強く連結されたコンポーネントであるため、コンポーネント内のすべてのポイントが相互に接続できることを意味します。したがって、ある地点から出発して、出発点に戻るためのループを見つけることができると想像するのは簡単です。このように、途中で通過するすべてのポイントは、強く接続されたコンポーネントの一部になります。

しかし、これには問題があり、強く連結されたコンポーネント内のすべてのポイントが漏れなく走査されるようにする必要があるということです。この問題の解決策としては、到達可能なすべてのポイントとパスを検索する検索アルゴリズムを使用するなど、さまざまな方法があります。しかし、そうすると別の問題に直面することになります。この問題は、強く連結されたコンポーネント間の接続性の問題です。

例を見てみましょう:

上の図では、ポイント 1 から開始すると、図内のすべてのポイントに到達できます。しかし、1、2、3 は強く連結されたコンポーネントであり、4、5、6 は別のコンポーネントであることがわかります。 1 が位置する強く連結されたコンポーネントを探すと、ポイント 4、5、および 6 も取り込まれる可能性が非常に高くなります。しかし問題は、それらが自己コンポーネントであり、1 の強連結コンポーネントにカウントされるべきではないということです。

以上の分析と考え方を整理すると、強連結成分分解アルゴリズムの核心は、実はこれら 2 つの問題、つまり完全性の問題を解決することであることがわかります。完全性とは、省略、冗長、エラーが一切ないことを意味します。核となる問題を理解すれば、思考の枠組みを構築するのは簡単です。そうすれば、アルゴリズムの説明がはるかに理解しやすくなります。

アルゴリズムの詳細

Tarjan アルゴリズムの最初のメカニズムはタイムスタンプです。これは、トラバース中にトラバースされた各ポイントに値がマークされることを意味します。この値は、走査された要素の数を示します。

これは簡単に理解できるはずです。グローバル変数を維持し、トラバース中にそれを増分するだけです。これを説明するために Python コードをいくつか書いてみましょう。

スタンプ = 0
 stamp_dict = {}def dfs(u):
    stamp_dict[u] = スタンプ スタンプ += 1
 Graph[u]のvの場合:
        dfs(v)

タイムスタンプを通じて、各ポイントが訪問された順序、つまり順方向の順序を知ることができます。たとえば、2 つの点 u と v があり、u のタイムスタンプが v のタイムスタンプよりも小さいとします。そうすると、それらの間の可能な関係は 2 つだけになります。1 つ目は、u を v に接続できることです。つまり、u から v へのリンクにアクセスできます。 2 つ目は、u を v に接続できないことです。この場合、v から u への逆接続を確立できるかどうかを議論するのは意味がありません。なぜなら、それらは互いに接続できないからです。

したがって、接続されたパスを見つけたい場合は、逆のパスも見つける必要があります。Kosaraju アルゴリズムでは、逆グラフを通じてこれを実現します。タージャンは別のアプローチを取った。各ポイントのタイムスタンプはすでにわかっているので、タイムスタンプを使用して逆方向のパスを見つけることができます。それは何を意味するのでしょうか? 実はとても簡単です。u をトラバースしているときに、u よりも小さいタイムスタンプを持つ v に遭遇した場合、u から v への逆パスがあることを意味します。この時点で v がスタックからポップされていない場合は、v が u の上流にあることを意味し、v から u へのパスがあることを意味します。これは、u と v が相互に接続できることを示しています。

相互に接続された u と v のペアが見つかったので、それを記録する必要があります。しかし、問題は、いつ記録を停止するかをどうやって知るかということです。境界はどこにあるのでしょうか。Tarjan アルゴリズムは、この問題を解決するための別の巧妙なメカニズムを設計しました。

このメカニズムはlowメカニズムであり、low[u]はポイントuが接続できるすべてのポイントの最小タイムスタンプを表します。タイムスタンプが小さいほど、検索ツリー内の位置が高くなります。これは、接続できる検索ツリーの最高点とも言えます。すると、この点が、点 u の強く連結された成分が配置されている検索ツリーのサブツリーのルートであることは明らかです。

少し混乱があるかもしれませんので、もう一度画像を見てみましょう。

グラフ内のノードのシリアル番号は、再帰トラバーサルのタイムスタンプです。グラフ上の各ポイントの最低値は 1 であることがわかります。検索ツリーでは、ポイント 1 がポイント 2、3、4 の祖先であることは明らかです。つまり、この強く接続されたコンポーネントのトラバースはポイント 1 から始まります。ポイント 1 がスタックからポップアウトされると、ルート 1 を持つサブツリーがトラバースされ、すべての可能な強連結コンポーネントが見つかったことを意味します。

これにより、別の疑問が生じます。現在のポイントが u であると仮定します。ポイント u が図の 1 のようなツリーのルートであるかどうかは、どうすればわかりますか? それをマークする方法はありますか?

もちろんあります。そのようなポイントには、タイムスタンプが最低値に等しいという特徴があります。したがって、見つかった強く接続されたコンポーネントを維持するために配列を使用し、これらの強く接続されたコンポーネントが通過できるツリー ルートがスタックからポップアウトされたときに配列をクリアすることができます。

上記のロジックを整理してコードを記述できます。

 scc = []
スタック = []
 def tarjan(u): dfn[u], low[u] = stamp, stamp stamp += 1
 スタックに追加(u)
 Graph[u]のvの場合:
        dfn[v]でない場合:
            tarjan(v) low[u] = min (low[u], low[v]) elif v がスタック内にある場合:
         low[u] = min (low[u], dfn[v]) dfn[u] == low[u]の場合:
        cur = [] # スタック内の u の後の要素は完全な強連結成分ですが、 Trueの場合:
            cur.append(スタック[-1])
            スタックポップ()
            cur[-1] == uの場合:
                壊す
        scc.append(現在)

最後に、前に話した典型的な例を見てみましょう。

まず、ポイント1から始めて、6まで深く探索します。6に到達すると、DFN[6]=4、low[6]=4になります。6がスタックからポップされると、条件が満たされ、6は独立して強く接続されたコンポーネントと呼ばれます。

同様に、5 が存在する場合、同じ条件が満たされ、2 番目の強く接続されたコンポーネントが得られます。

次に、ノード 3 まで遡ります。ノード 3 はノード 4 まで移動することもでき、ノード 4 はノード 1 に接続できます。ポイント 1 はすでにスタック内にあるため、ポイント 1 は再帰されず、low[4] = 1 のみが更新されます。同様に、ポイント 4 が終了すると、ポイント 3 が更新され、low[3] = 1 になります。

最後に、ノード 1 に戻り、ノード 1 を経由してノード 2 に移動します。2 が接続できる 4 つのポイントはすでにスタック内に存在し、DFN[4] > DFN[2] であるため、ポイント 2 は更新されません。再びポイント1に戻ると、ポイント1に接続できる他のポイントがないので終了します。終了時にlow[1] = DFN[1]であり、スタック内の残りの4つの要素はすべて強く接続されたコンポーネントであることがわかります。

これでアルゴリズム全体の流れの紹介は終了です。本日の内容を楽しんでいただければ幸いです。