DFS，在无向图中寻找圆
DFS , finding circle in undirected graph
这是我处理这个问题的方法。但似乎这并不像我预期的那样有效。怎么了？
def dfs(graph, start, visited = None):
'''find if there is a circle in the graph, if there is ,return True'''
if visited == None:
visited = set()
visited.add(start)
for next in graph[start]:
if next in visited:
return True
else:
dfs(graph, next, visited)
return False
因为它是一个无向图，你必须照顾当前节点的父节点，假设你从节点1到节点2，然后在遍历节点2的边时你会再次找到节点1并且它有已经被访问过，所以答案会 return 为真，即循环存在，但情况可能并非如此，因此您需要添加另一个参数来检查相邻节点是否不是当前节点的父节点。这里的父节点是指DFS遍历中当前节点的直接前驱。
这是我处理这个问题的方法。但似乎这并不像我预期的那样有效。怎么了？
def dfs(graph, start, visited = None):
'''find if there is a circle in the graph, if there is ,return True'''
if visited == None:
visited = set()
visited.add(start)
for next in graph[start]:
if next in visited:
return True
else:
dfs(graph, next, visited)
return False
因为它是一个无向图，你必须照顾当前节点的父节点，假设你从节点1到节点2，然后在遍历节点2的边时你会再次找到节点1并且它有已经被访问过，所以答案会 return 为真，即循环存在，但情况可能并非如此，因此您需要添加另一个参数来检查相邻节点是否不是当前节点的父节点。这里的父节点是指DFS遍历中当前节点的直接前驱。