グラフの相互エッジを検出する

Question

私はグラフの隣接リスト表現を持っていますが、対称ではありません。ノードAのエッジがBである場合、BのエッジがAであることは真ではありません。私はこれが有向グラフ（有向グラフ）になると思う。

ノードからすべての双方向パスを検出するには、どのような方法が適していますか。私は、DFSを使用してノードからグラフの別のノードへのパスを検出できることを知っています。私が探しているのは、双方向エッジのみを考慮した双方向DFSです。

これを行う1つの方法は、ノードの隣人を見て、これが双方向関係であるかどうかを調べることです。しかし、このためには、この隣接ノードのすべての即時接続を調べ、最初のノードも接続であるかどうかを確認し、そうであれば再帰を続行する必要があります。これを効率的に行う方法があるのだろうか？

Answer 1

ノードから出てくるエッジを表すためにリストの代わりに何らかのセットデータ構造（ハッシュまたはツリーベース）を使用する、かなり標準的な「隣接セット」表現を使用すると、グラフ内にエッジの逆のバージョンが存在する。隣接リスト表現からの隣接セット表現の構築は、直観的なものである。

また、グラフ内のすべての辺の1つのセットを作成し、反転されたバージョンがセット内にないグラフから辺をフィルタリングすることができます。これは、他のアプローチでそれを使用した後で、隣接セット表現のためにそれ以上使用する必要がない場合に、より便利になります。メモリ使用量を抑えたい場合は、グラフ内で逆のバージョンを見つけた場合にはそのセットからエッジを削除し、反転したバージョンではなくセット内にある場合は後でエッジからグラフを削除することができますそうではありません。