問題タブ [kosaraju-algorithm]

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

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

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

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

課題の一部として、大きなグラフに Kosaraju のアルゴリズムを実装しようとしています [MOOC Algo I Stanford on Coursera]

https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm

現在のコードは小さなグラフで動作しますが、実行時にスタック オーバーフローが発生します。

Expert in F# の関連する章、または Web サイトや SO で利用可能な他の例を読んだにもかかわらず、この問題を解決するために継続を使用する方法がまだわかりません

以下は汎用の完全なコードですが、DFSLoop1 と再帰関数 DFSsub を内部で実行すると、既に失敗します。私は関数の末尾を再帰的にしていないと思います[命令のため

?]

しかし、継続を適切に実装する方法がわかりません。

失敗した部分だけを考えると、DFSLoop1 は深さ優先探索を適用するグラフを引数に取っています。2 番目の DFS ループ (DFSLoop2) でアルゴの 2 番目の部分に進むには、アルゴの一部として終了時刻を記録する必要があります [もちろん、その前に失敗しています]。

これは、単純なグラフの例を含むテキスト ファイルです。

(オーバーフローを引き起こしているのは、約 900,000 ノードで 70Mo の大きさです)

編集

最初にいくつかのことを明確にするために、これが「疑似コード」です

入力: 有向グラフ G = (V,E)、隣接リスト表現。頂点 V が 1、2、3、. . . 、n。1. すべてのアークの向きが逆になった後のグラフ G を Grev とします。2. Grev で DFS-Loop サブルーチンを実行し、与えられた順序に従って頂点を処理し、各頂点 v ∈ V の終了時刻 f(v) を取得します。3. G で DFS ループ サブルーチンを実行し、f(v) の降順に頂点を処理して、各頂点 v ∈ V にリーダーを割り当てます。4. G の強連結成分は、共通のリーダーを共有する G の頂点に対応します。 図 2 : SCC アルゴリズムのトップレベル。f 値とリーダーは、それぞれ DFS-Loop の 1 回目と 2 回目の呼び出しで計算されます (以下を参照)。

入力: 有向グラフ G = (V,E)、隣接リスト表現。1. グローバル変数 t を 0 に初期化します。[これにより、完全に探索された頂点の数が追跡されます。] 2. グローバル変数 s を NULL に初期化します。[これは、最後の DFS 呼び出しが呼び出された頂点を追跡します。] 3. i = n downto 1 の場合: [最初の呼び出しでは、頂点に 1、2、. . . 、 n 任意。2 番目の呼び出しでは、頂点は最初の呼び出しの f(v) 値によってラベル付けされます。] (a) i がまだ探索されていない場合: i. s := i を設定 ii. DFS(G, i) 図 3 : DFS-Loop サブルーチン。

入力: 隣接リスト表現の有向グラフ G = (V,E)、およびソース頂点 i ∈ V 。1. i を探索済みとしてマークします。[DFS-Loop 呼び出しの全期間にわたって探索されたままです。] 2. Leader(i) := s を設定します。 3. 各アーク (i, j) ∈ G について: (a) j がまだ探索されていない場合: i. DFS(G, j) 4. t + + 5. f(i) := t を設定 図 4 : DFS サブルーチン。f 値は、DFS-Loop への最初の呼び出し中にのみ計算する必要があり、リーダー値は、DFS-Loop への 2 回目の呼び出し中にのみ計算する必要があります。

EDIT 経験豊富なプログラマー (リスパーだが F# の経験がない) の助けを借りてコードを修正し、最初の部分をいくらか単純化して、この議論に関係のないコードを気にすることなく、より迅速に例を示しました。

コードはアルゴの半分のみに焦点を当てており、DFS を 1 回実行して逆ツリーの終了時刻を取得します。

これは、小さな例を作成するためのコードの最初の部分です。y は元の木です。タプルの最初の要素は親で、2 番目の要素は子です。しかし、逆ツリーで作業します

したがって、基本的にグラフは (1->2->3->1)::(4->5->6->7->8->....->99999->10000) と逆のグラフですは (1->3->2->1)::(10000->9999->....->4)

ここに直接スタイルで書かれたメインコードがあります

末尾再帰ではないため、継続を使用します。これは、CPS スタイルに適応した同じコードです。

両方のコードがコンパイルされ、小さな例 (コメントのもの) または使用している同じツリーで同じ結果が得られますが、サイズは小さくなります (100000 ではなく 1000)。

ここのアルゴリズムのバグではないと思います。同じツリー構造を持っていますが、大きなツリーが問題を引き起こしているだけです。続きがよく書かれているように見えます。コードを明示的に入力しました。そして、すべての呼び出しは、すべての場合に継続で終了します...

専門家のアドバイスをお待ちしています!!! ありがとう ！！！