在 Python 中检查图形中是否有任何常见的可到达节点的程序

假设我们有一个有向图的边列表，有 n 个节点，节点名称是 0 到 n-1。我们还有两个整数值 a 和 b。我们必须检查是否存在任何节点 c 以便我们可以从 c 到 a 以及从 c 到 b。

所以，如果输入像

并且 a = 2, b = 3，那么输出将为 True，因为这里 c = 0，所以我们有从 0 到 2 以及从 0 到 3 的路线。

示例

让我们看看以下实现以更好地理解 -

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