用 Python 编写程序检查图中是否存在任何公共可达节点
pythonserver side programmingprogramming更新于 2026/1/11 13:32:17
假设我们有一个有向图的边列表，其中有 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、visited
- 如果 node 未被访问，则
- 将节点标记为已访问
- 对于 graph[node] 中的每个 x，执行
- DFS(graph, x, visited)
- 从 main 方法中，执行以下操作 −
- 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
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
