【Python】グラフ内の2つのノードに共通して到達可能なノードが存在するかを判定するプログラム

問題概要

有向グラフのエッジリストが与えられます。グラフは n 個のノードから構成され、ノード名は 0 から n-1 までです。さらに、2つの整数値 a と b が与えられます。ここで、「あるノード c から a への経路と、c から b への経路がどちらも存在する」という条件を満たすノード c が存在するかどうかを判定するのが課題です。

例として、下図のようなグラフを考えてみましょう。

a = 2、b = 3 の場合、出力は True になります。これは c = 0 とおくと、0 から 2 への経路と 0 から 3 への経路がどちらも存在するためです。

解法の考え方：逆グラフとDFSの組み合わせ

この問題は深さ優先探索（DFS）を使えば効率的に解くことができます。鍵となるのは、エッジの向きをすべて反転させた「逆グラフ」を事前に作成しておく点です。

逆グラフ上であるノード a から DFS を実行すると、「a に到達可能なすべてのノード」を列挙できます。同じ操作を b に対しても行い、得られた2つの訪問済みノード集合の共通部分を調べればよいのです。共通部分が空でなければ、その要素こそが「a にも b にも到達できるノード c」に該当します。

アルゴリズムの手順

• DFS関数を定義する（引数： graph, node, visited）
  • node が未訪問の場合：
    • node を訪問済みとしてマークする
    • graph[node] 内の各ノード x に対して、DFS(graph, x, visited) を再帰的に呼び出す
• メイン処理（solve関数）では以下を実行する：
  • エッジリストから隣接リスト形式の逆グラフを生成する
  • 空の集合 visited_a と visited_b を用意する
  • DFS(graph, a, visited_a) を実行する
  • DFS(graph, b, visited_b) を実行する
  • visited_a と visited_b の共通部分を新しいリストとして取得する
  • 共通部分が空でなければ True を返し、空なら False を返す

Pythonでの実装例

それでは、実際のコードを見てみましょう。

def edge_list_to_graph(edges):
    s = set()
    for x, y in edges:
        s.add(x)
        s.add(y)
    s = len(list(s))
    graph = [[] for x in range(s)]
    for x, y in edges:
        graph[y].append(x)
    return graph

def DFS(graph, node, visited):
    if node not in visited:
        visited.add(node)
        for x in graph[node]:
            DFS(graph, x, visited)

def solve(edges, a, b):
    graph = edge_list_to_graph(edges)

    visited_a, visited_b = set(), set()

    DFS(graph, a, visited_a)
    DFS(graph, b, visited_b)

    ans = list(visited_a.intersection(visited_b))
    if ans:
        return True
    return False

ed_list = [(0, 4),(4, 3),(1, 2),(0, 1),(0, 2),(1, 1)]
a = 2
b = 3
print(solve(ed_list, a, b))

入力

[(0, 4),(4, 3),(1, 2),(0, 1),(0, 2),(1, 1)], 2, 3

出力

True

コードのポイント解説

• edge_list_to_graph関数： エッジリストに登場する全ノードを一旦集合に集めてノード総数を求め、そのサイズ分の隣接リストを初期化します。注目すべきは graph[y].append(x) の部分で、エッジ (x, y) を逆向き（y → x）として登録しています。これにより逆グラフが構築されます。
• DFS関数： 再帰的な深さ優先探索の標準的な実装です。訪問済みノードは set で管理しているため、追加や存在確認が O(1) で行えるのが利点です。
• solve関数： a と b それぞれからの DFS 結果を set の intersection() メソッドで照合し、共通ノードが存在するかどうかを判定します。

計算量

ノード数を V、エッジ数を E とすると、各 DFS の計算量は O(V + E) であり、共通部分の算出は O(V) で済みます。したがって、全体の計算量は O(V + E) となり、非常に効率的なアプローチだと言えます。