コサラジュのアルゴリズム: 強結合コンポーネント ガイド

TL;DR: コサラジュのアルゴリズムは、2 つのパスを使用して有向グラフ内の強連結成分を検出します深さ優先検索パス。まず終了時間を減らして頂点を記録し、すべてのエッジを転置し、転置されたグラフをその順序で探索します。転置が格納されるときの実行時間は O(V + E)、補助記憶域は O(V + E) です。

コサラジュのアルゴリズムとは何ですか?

Kosaraju のアルゴリズムは、有向グラフを強接続コンポーネント (SCC) に分割します。 1 つの SCC 内では、すべての頂点が他のすべての頂点に到達できます。各 SCC を 1 つのノードに縮小すると、有向非巡回グラフが生成され、コンポーネントが依存関係の分析、プログラム グラフ、到達可能性、およびグラフの圧縮に役立ちます。

このアルゴリズムは、深さ優先検索の構造的特性を使用します。元のグラフの終了時間により、転置されたグラフを探索するための安全な順序が特定されます。すべてのエッジを反転すると、コンポーネント間のソースとシンクの関係が交換されるため、頂点が正しい順序で処理される場合、1 回の検索が割り当てられていないコンポーネントに漏れることはありません。

2 パス アルゴリズムはどのように機能しますか?

1. 訪問セットと空の着順リストを作成します。
2. 元のグラフ内の未訪問の頂点すべてから深さ優先検索を実行します。
3. すべての発信隣接頂点が終了した後に、各頂点を追加します。
4. すべての有向エッジを反転して転置を構築します。
5. 訪問済みセットをクリアします。
6. 逆の終了順序で頂点を処理します。
7. 転置グラフ内の各 DFS ツリーは、1 つの強く接続されたコンポーネントです。

最初の DFS 呼び出しが返されたときに、頂点をスタックに保存できます。スタックをポップすると、自然に終了時間が短縮されます。グラフが切断されている可能性があるため、両方の外側のループは頂点 0 のみから開始するのではなく、すべての頂点を考慮する必要があります。

終了順序を逆転すると SCC が見つかるのはなぜですか?

すべての SCC を 1 つのノードに圧縮することを想像してください。結果として得られる凝縮グラフには有向サイクルがありません。最初の DFS では、関連する終了時間が最も遅いコンポーネントが、この凝縮された構造内のソースのように動作します。グラフを転置した後、そのコンポーネントはシンクのように動作するため、そこで開始された DFS は内部に残ります。

そのコンポーネントを削除すると、次の未割り当てコンポーネントの同じ引数が明らかになります。これは面接官が通常望んでいる証明のアイデアです。終了順序によってコンポーネントが安全に選択され、転置によって 2 番目のパスが間違った出力境界を越えるのが防止されます。長い正式な証明を再現する必要はありませんが、両方の役割を説明する必要があります。

時間と空間の複雑さは何ですか?

各深さ優先検索パスでは、すべての頂点を訪問し、すべてのエッジを 1 回検査します。また、転置の構築にも直線的な時間がかかります。したがって、合計時間は O(V + E) となります。グラフと転置の両方の隣接リストを使用すると、ストレージは O(V + E) に、訪問状態、終了順序、再帰または明示的なスタック用に O(V) を加えます。

非常に深いグラフの場合、再帰的 DFS は言語の呼び出しスタック制限を超える可能性があります。反復スタックについて言及すると、漸近限界を変更せずに本番環境を認識していることがわかります。

面接のために知っておくべき疑似コードは何ですか?

``テキスト 終了順序 = [] 訪問済み = set()

グラフの頂点の場合: 頂点が訪問されていない場合: dfs_finish(頂点、グラフ、訪問済み、finish_order)

transpose = reverse_all_edges(グラフ) 訪問済み.clear() コンポーネント = []

逆方向の頂点の場合(finish_order): 頂点が訪問されていない場合: コンポーネント = [] dfs_collect(頂点、転置、訪問済み、コンポーネント) コンポーネント.追加(コンポーネント) 「」

dfs_finish で、近傍を訪問した後に頂点を追加します。 dfs_collectでは、頂点が見つかったら追加します。これら 2 つの責任は分けておいてください。最初のパスで preorder を使用することはよくあるエラーです。

コサラジュの実装を壊す一般的な間違いはどれですか?

最も一般的な間違いは、終了順序ではなく検出順序を記録する、2 番目のパスの順序を逆にするのを忘れる、一部のエッジのみを反転する、訪問済みの状態をクリアせずに再利用する、孤立または切断された頂点をスキップするなどです。もう 1 つの間違いは、無向グラフを SCC が同じように意味があるかのように扱うことです。接続されたコンポーネントは、より単純な概念です。

単一の頂点、孤立した頂点、1 つの有向サイクル、一方向チェーン、1 つのエッジで結合された 2 つのサイクル、自己ループ、および切断されたグラフをテストします。有効な DFS 走査順序が異なると、コンポーネントまたは頂点のリストが異なる可能性があるため、コンポーネントの出力順序に依存するのではなく、パーティションを検証してください。

コサラジュは Tarjan のアルゴリズムとどう比較しますか?

どちらのアルゴリズムも O(V + E) で SCC を見つけます。 Kosaraju は 2 つの DFS パスを使用し、通常は転置されたグラフを保存するため、推論と実装が簡単になります。 Tarjan は、検出インデックス、低リンク値、およびスタックを備えた 1 つの DFS を使用します。明示的な転置を回避しますが、より多くの状態を正しく維持できます。

面接では、制約がある場合を除き、説明して確実に実装できるアルゴリズムを選択してください。面接官が 1 回のパスまたは移調なしを要求した場合は、Tarjan の方が適している可能性があります。明確さと直接的な証明が優先される場合は、多くの場合、Kosaraju が優れた選択肢となります。

AI はグラフ アルゴリズムの実践を責任を持ってサポートするにはどうすればよいですか?

AI は、小さな反例を生成し、DFS 状態をトレースし、実装を比較し、複雑さの説明に異議を唱えることができます。コーディング支援は順序付けや訪問状態のバグを見つけるのに役立ちますが、トランスクリプトのレビューは証明のアイデアを明確に説明したかどうかを示すことができます。

常に少なくとも 1 つのグラフを自分で描画およびトレースし、テストを実行して、生成されたクレームを検証してください。評価ルールに従い、禁止されている支援を使用しないでください。 YesToTheOffer は、コーディングの準備、許可されたリアルタイム推論、個人的なメモ、および面接後のレビューをサポートします。

よくある質問

練習を再現可能なシステムに変える

証拠に基づいた練習計画を立て、許可されている場合は責任あるサポートを利用し、新鮮なうちに会話を見直します。