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)
  • 在主方法中，执行以下操作：
  • graph := 从edge_list生成邻接表
  • visited_a, visited_b := 两个空集合
  • 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

更新于：2021年10月16日

290 次浏览

启动您的职业生涯

完成课程获得认证

开始学习
广告