グラフに共通の到達可能なノードがあるかどうかをPythonでチェックするプログラム

有向グラフのエッジリストがあり、ノードがn個あり、ノード名が0〜n-1であるとします。2つの整数値aとbもあります。 cからaに、またcからbに移動できるようなノードcがあるかどうかを確認する必要があります。

したがって、入力が次のような場合

また、a =2、b =3の場合、出力はTrueになります。これは、ここではc =0であるため、0から2、さらには0から3へのルートがあります。

これを解決するには、次の手順に従います-

• 関数DFS（）を定義します。これは、グラフ、ノード、訪問済みを取得します
• ノードにアクセスしていない場合は、
  • ノードを訪問済みとしてマーク
  • グラフ[ノード]のxごとに、
    を実行します。
    • DFS（グラフ、x、訪問済み）
• メインの方法から、次の手順を実行します-
• グラフ：=edge_listから隣接リストを生成する
• visited_a、visited_b：=2つの空のセット
• DFS（graph、a、visited_a）
• DFS（graph、b、visited_b）
• ans：=visited_bとvisited_aの交差点からの新しいリスト
• ansが空でない場合は、
  • Trueを返す
• Falseを返す

例

理解を深めるために、次の実装を見てみましょう-

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