在Python中检查图形中是否存在任何可达的共同节点的程序

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

因此，如果输入为

且a = 2，b = 3，则输出为True，因为在这里c = 0，因此我们有从0到2和0到3的路线。

为了解决这个问题，我们将遵循以下步骤 –

• 定义一个函数DFS()。 这将取图，节点，已访问
• 如果节点未被访问，则
  • 将节点标记为已访问
  • 针对graph[node]中的每个x执行以下操作
    • DFS(graph，x，visited)
• 从主要方法中执行以下操作 –
• 图：=从edge_list生成邻接列表
• visited_a，visited_b：=两个空集合
• DFS(graph，a，visited_a)
• DFS(graph，b，visited_b)
• ans：=从visited_a和visited_b的相交处中获取新列表
• 如果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