algorithm - コサラジュのアルゴリズムでグラフの補数に対して DFS を実行する必要があるのはなぜですか?

Question

と呼ばれる強連結成分を見つけるための有名なアルゴリズムがあります。このアルゴリズムは、Kosaraju's algorithm2 つの DFS を使用してこの問題を解決し、θ(|V| + |E|)時間内に実行されます。

最初に、グラフの補数 ( G^R )で DFS を使用して頂点の逆後順を計算し、次に頂点Gを逆後順で取得して強連結成分を計算することにより、メイン グラフに 2 番目の DFS を適用します。

アルゴリズムの仕組みは理解していますが、逆のポスト オーダーの必要性の背後にある直感を理解していません。

2 番目の DFS が強連結成分を見つけるのにどのように役立ちますか?

Answer 1

最初の DFS の結果は次のとおりです。

----------v1--------------v2-----------

ここで、「-」は任意の数を示し、強連結成分gのすべての頂点はv1とv2の間に現れます。

ポストオーダーによる DFS は、次のことを保証します。

• v2の後のすべての頂点は逆グラフのgを指しません(つまり、元のグラフのgからこれらの頂点に到達することはできません)。
• 逆グラフのgからv1より前のすべての頂点を指すことはできません(つまり、元のグラフのこれらの頂点からgに到達することはできません)。

一言で言えば、最初の DFS は、2 番目の DFS で、以前にアクセスされた強連結コンポーネントが、他の未アクセスの強連結コンポーネントへのエッジ ポイントを持つことができないことを保証します。

詳細な説明

次のようにグラフを単純化しましょう。

• グラフ全体が G
• G には 2 つの強連結成分が含まれます。1 つはgで、もう 1 つは単一の頂点vです。
• vとgの間には、 vからgまたはgからvのいずれかのエッジが 1 つしかありません。このエッジの名前はeです。
• g' , e'はg , eの逆を表す

このアルゴリズムが失敗する可能性がある状況は、次のように結論付けることができます。

1. vから DFS を開始し、e'はvからg'を指す
2. g'内の頂点から DFS を開始し、e'はg'からvを指す

状況 1 の場合

元のグラフは のようg-->vになり、逆のグラフは のようになりg'<--vます。

v から 2 番目の DFS を開始するには、最初の DFS によって生成されるポスト オーダーが次のようになる必要があります。

g1, g2, g3, ..., v

しかし、 vからもg'からも最初の DFS を開始しても、そのようなポスト オーダーが得られないことは簡単にわかります。したがって、この状況では、2 番目の DFS が両方の頂点から開始しないことが最初の DFS であることが保証されます。から外れており、強連結成分を指しています。

状況 2 の場合

状況 1 と同様に、元のグラフがg<--vであり、反転したグラフが である状況 2 では、 vがg 'のどの頂点よりも前にアクセスg'-->vされることが保証されます。