满足条件时中断递归函数

Question

我正在尝试使用深度优先搜索(DFS(构建一个简单的循环检测算法。该算法的工作原理如下：在某个节点上执行DFS(目前只假设整个图是连接的(，并将当前正在使用的任何节点标记为灰色，如果完成，则标记为黑色。如果当前节点具有灰色邻居，则退出该功能并打印"0"；检测到周期"；

这是我的代码，使用一个简单的4节点图

from collections import defaultdict
G = {'F': ['X', 'O'], 'X': ['F', 'F'],'O':[]}
V = set(G.keys())
gray, black = set(), []
def dfs(u):
try:
print('-'*30,"n",u)
gray.add(u)
for v in G[u]:
if v in gray:
raise ValueError
elif v not in black:
dfs(v)
gray.discard(u)
black.append(u)
except:
return True
if dfs('F'):
print('Cycle detected')

我原以为这个尝试会奏效，但事实并非如此。

最后，我知道我可以使用一个可变变量，如cycle=[False]，并在满足条件的情况下将其更新为true。我在问如何避免这样做！谢谢

Answer 1

算法没有被破坏。它可以固定如下：

删除try，except模式，用替换adj顶点上的循环

for v in G[u]:
if v in gray:
return True
elif v not in black:
if dfs(v):
return True

if中的dfs(v(执行双重任务，打开递归调用并检索其输出。由于此返回位于最外层的递归中，并且在前面提到的返回语句之后，因此当最内层的递归返回True时，它将自动停止进一步的搜索并返回True。