有向グラフのすべての弱結合成分を見つけるアルゴリズム

有向グラフ内の弱く結合した成分をすべて見つけるアルゴリズムを探しています。無向グラフの場合は、dfs経由でこれを行うことができますが、これは有向グラフの場合は明らかです。グラフを隣接リストとして保存しています。例えば：有向グラフのすべての弱結合成分を見つけるアルゴリズム

A -> B 
B -> C 
D -> X

SO-B-Cは、連結成分D-X

Iが強連結成分を見つけるためのアルゴリズムを探しておりませんです！

出典

2016-03-18 Exagon

さて、あなたは、あなたが有向グラフにおける連結成分について話している意味される正確な必要があります。接続されたコンポーネントを「無関係な方法」で意味しますか？ – mingaleg

私が知っている限り、有向グラフには接続されたコンポーネントがありません。弱く接続されたコンポーネントについて話すことができます（dfs +グラフを無向にするだけです）。あなたは有向グラフの接続されたコンポーネントの意味をよりよく定義できますか？ – mancuernita

いいえ、すべてのエッジを無向にして、コンポーネントを見つけてください。 – mingaleg

メモリの制約が厳しくなければ、2番目の一時的な隣接リストを保持できます。その2番目の隣接関係リストでは、各エッジをa→bとし、エッジを逆方向に配置します。（つまり、b-> a）次に、その隣接リストでDFSを使用して、接続されたコンポーネントを見つけることができます。

出典

2016-03-18 18:29:24 ilim

は、実際には各エッジに逆を格納するだけで、必要なスペースを削減する必要があります。 – Paul

私は、有向グラフを無向グラフに変換することを概念化する方が簡単だと考えました。結局のところ、空間の複雑さは同じです。あなたは明らかに正しいです。これは、元のグラフのエッジを2回保存しないために必要なスペースを半分にします。 – ilim

非常に簡単な解決法は、次のようになります。
与えられたグラフから無向グラフを作成することから始めます。コピーを作成し、各エッジの逆をエッジのセットに追加するだけです。頂点のセットのコピーを作成し、任意の頂点で開始し、頂点を含むコンポーネントをDFSトラバースし、すべての移動ノードをセットから削除してリストに追加します。リストが空になるまでこれを繰り返します。擬似コードで

：

bimap edges 
edges.putAll(graph.edges()) 

set vertices = graph.vertices() 

list result 

while !vertices.isEmpty() 
    list component 

    vertex a = vertices.removeAny() 
    dfsTraverse(a , v -> { 
     vertices.remove(v) 
     component.add(v) 
    }) 

    result.add(component)

出典

2016-03-18 22:34:36 Paul

有向グラフのすべての弱結合成分を見つけるアルゴリズム

答えて

関連する問題