問題タブ [strongly-connected-graph]

有向グラフが強く接続されているかどうか、つまり、他のノードがすべてのノードに到達できるかどうかを確認する必要があります（必ずしも直接エッジを経由する必要はありません）。

これを行う1つの方法は、すべてのノードでDFSとBFSを実行し、他のすべてのノードがまだ到達可能であることを確認することです。

それを行うためのより良いアプローチはありますか？

私は独学でグラフ理論を試しており、グラフでSCCを見つける方法を理解しようとしています。SO に関するいくつかの異なる質問/回答 (例: 1、2、3、4、5、6、7、8 ) を読みましたが、従うことができる完全なステップバイステップの例を含むものを見つけることができません。

CORMEN (Introduction to Algorithms)によると、1 つの方法は次のとおりです。

1. DFS(G) を呼び出して、各頂点 u の終了時刻 f[u] を計算します
2. 転置計算(G)
3. DFS(Transpose(G)) を呼び出しますが、DFS のメイン ループでは、(ステップ 1 で計算されたように) f[u] が減少する順序で頂点を考慮します。
4. ステップ 3 の深さ優先フォレスト内の各ツリーの頂点を個別の強連結成分として出力します。

次のグラフを観察してください (質問はここから 3.4です。こことここでいくつかの解決策を見つけましたが、これを分解して自分で理解しようとしています。)

ステップ 1: DFS(G) を呼び出して、各頂点 u の終了時刻 f[u] を計算する

頂点 A から開始する DFS の実行:

[Pre-Vist, Post-Visit] としてフォーマットされた赤いテキストに注意してください。

ステップ 2: Transpose(G) を計算する

ステップ 3. DFS(Transpose(G)) を呼び出しますが、DFS のメイン ループでは、(ステップ 1 で計算したように) f[u] の降順で頂点を考慮します。

では、訪問後 (終了時間) の値が減少する順に頂点を示します。

{E、B、A、H、G、I、C、D、F、J}

したがって、このステップでは、G^T で DFS を実行しますが、上記のリストの各頂点から開始します。

• DFS(E): {E}
• DFS(B): {B}
• DFS(A): {A}
• DFS(H): {H、I、G}
• DFS(G): すでに訪問されているため、リストから削除します
• DFS(I): すでに訪問されているため、リストから削除します
• DFS(C): {C、J、F、D}
• DFS(J): すでに訪問されているため、リストから削除します
• DFS(F): すでに訪問されているため、リストから削除します
• DFS(D): すでに訪問されているため、リストから削除します

ステップ 4: ステップ 3 の深さ優先フォレスト内の各ツリーの頂点を個別の強連結成分として出力します。

したがって、{E}、{B}、{A}、{H、I、G}、{C、J、F、D} の 5 つの強連結成分があります。

これが私が正しいと信じていることです。ただし、こことここで見つけた解決策では、SCC は {C、J、F、H、I、G、D} および {A、E、B} であると言われています。私の間違いはどこですか？

グラフが強く接続されているかntであるかを確認するためにnetworkx（初めて）を使用していますが、定義されていないことがわかりました。ドキュメントが述べたように、それは動作するはずです.??

私の実行：

トレースバック (最新の呼び出しが最後): ファイル ""、1 行目、

NameError: 名前 'is_strongly_connected' が定義されていません

ありがとう

私は MATLAB で画像操作プログラムのプロトタイプを作成しており、プロトタイプ作成段階が完了したら、それを JavaScript に移植したいと考えています。

私は JavaScript にあまり詳しくありませんが、利用可能な画像処理ライブラリがたくさんあるようです。そのため、MATLAB で使用する基本的な画像操作関数のほとんどは、既にどこかに実装されていると思います。ただし、MATLAB で使用しているより強力な関数の 1 つは「regionprops」と呼ばれ、基本的にバイナリ イメージの強く接続されたコンポーネントを計算し、領域、境界などの各「コンポーネント」に関連する一連の統計情報を出力します。ボックス、重心など

これを js で利用できるようにするための最短の方法 (つまり、私の部分での最小限の実装) は何ですか? 最後の手段として、強く接続されたコンポーネント ライブラリを使用するために画像をグラフに変換します。これを回避できる場合 (およびその後の画像関連の計算) を知りたいです。

ドキュメントとライブラリへのポインタは大歓迎です! ありがとう、テップ。

Kosaraju のアルゴリズムでは、逆グラフから終了時刻が生成されます。次に、DFS を実行することにより、元のグラフから、以前に生成された最大の終了時刻から最小の終了時刻まで、強連結成分が検出されます。

Kosaraju のアルゴリズムの終了時間は、元のグラフから生成できますか? では、最低終了時間から最高終了時間まで DFS を実行すると、強連結成分を発見できるでしょうか?

私にはそのように思えますが、それは私の直感です。

私は、neo4j-mazerunnerを使用して、グラフ上の strong_connected_components 関係を分析しました。プロセスが終了し、ノードでstrong_connected_componentsプロパティを取得しました。

次のクエリを使用して、ノードの異なるノードの行を取得しました。

生成されたクラスターを視覚化するためにグラフを暗号クエリする方法がわかりません。

どんな助けでも感謝されます。

Tarjan の強連結グラフ アルゴリズム ( https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm ) を実装しようとしています。ここに私のコードがあり、なぜ頂点4と頂点5も強連結成分として出力されるのか混乱していますか?

テストするノードが 5 つしかない非常に単純なダイアグラムを使用しています。私のコードは Python 2.7 で書かれています。