在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
示例
让我们看下面的实现以更好地理解 –