python - 如何使用 DFS 正确检测循环?
问题描述
这是我在图中检测循环的代码:
seen = set()
def check(table,node):
seen.add(node)
#traverse all neighors of the current node
for neigh in table[node]:
print(neigh, seen)
if neigh not in seen:
check(table,neigh)
else:
return False
return True
table1 = {'A':['B'],'B':['A']}
print(check(table1,'A'))
为什么它总是返回 True?即使存在循环,else 子句也不会执行。我错过了什么吗?谢谢!
解决方案
我认为问题在于您需要返回递归调用check
(在 if 语句之后)使您的代码看起来像:
seen = set()
def check(table,node):
seen.add(node)
#traverse all neighors of the current node
for neigh in table[node]:
print(neigh, seen)
if neigh not in seen:
return check(table,neigh)
else:
return False
return True
table1 = {'A':['B'],'B':['A']}
print(check(table1,'A'))
您的原始代码会发生什么情况是您使用节点“B”递归调用 check,它返回 false,但您不对该返回值执行任何操作,因此在顶层它退出 for 循环并向用户返回 true。希望这可以帮助你!
推荐阅读
- html - CSS中断表并重复第一列
- ios - 可以访问选项值而不是仅选择索引的自定义选择器
- html - 将插件集成到 html 和 css 模板中
- php - 推送器未触发事件不起作用 Laravel
- avx512 - AVX-512 Galois-field 相关指令有什么用途?
- python - 使用请求下载有限制的图像
- amazon-web-services - 是否可以向使用 AWS Amplify 预置的 lambda PostAuthenticate 函数授予额外权限?
- python - 在烧瓶中将数据渲染为 html:如何通过 app.route 函数烧瓶传递数据?
- gradle - 如何使用 gradle 获取空手道测试功能文件的 Jacoco 报告
- c++ - 从文件 .txt 中读取数据