如何使用 dfs 在图中查找桥？

Question

我正在尝试检查给定图中是否存在桥，但它总是返回 false。
请让我明白，为什么会这样？

这是我的代码：-

def dfs(graph, node, visited,intime,lowtime, par):
    global timer
    visited[node] = True
    intime[node] = timer
    lowtime[node] = timer
    timer += 1

    for child in graph[node]:
        if not visited[child]:
            dfs(graph, child, visited,intime,lowtime, node)
            if intime[node]< lowtime[child]:
                print('bridge found between nodes', node,'-', child)
                return True

            lowtime[node] = min(lowtime[node], lowtime[child])
        else:
            if child != par:
                lowtime[node] = min(lowtime[node], intime[child])
        # return True
    return False

这是此功能的驱动程序代码：-

#Driver code

inp = [[1,2],[1,3],[2,4],[3,4],[3,5],[5,6],[5,7],[6,7]] 
n = 7 #node
graph = {}
visited = {}

intime = {}  #time of contact with node
lowtime = {}
timer = 1

for i in range(1, n+1):
    graph[i] = []
    visited[i] = False
    intime[i] = None
    lowtime[i] = None
for u,v in inp:
    graph[u].append(v)
    graph[v].append(u)

print(dfs(graph,1,visited,intime, lowtime, -1))

输出：

bridge found between nodes 3 - 5
False

我想，我已经正确地实现了功能（因为它打印正确，即 bridge found between nodes 3 - 5），但不知道递归在内部是如何工作的。

谢谢:)

Answer 1

打印 false 的原因是因为你在 dfs for 循环的末尾总是 return False。您已成功找到您的桥梁，因为倒数第二个 for 循环迭代 returns True!! ;) 如果将 print(child,visited[child],visited) 添加为 dfs for 循环中的第一行，您可以看到更多详细信息：

如何使用 dfs 在图中查找桥？

How to find bridges in a graph using dfs?

python

algorithm

graph