时间戳

首页 > 解决方案 > 条件满足时跳出递归函数

python-3.x - 条件满足时跳出递归函数

问题描述

我正在尝试使用深度优先搜索（DFS）构建一个简单的循环检测算法。该算法的工作原理如下：在某个节点上执行 DFS（目前只假设整个图是连接的）并将当前正在使用的任何节点标记为灰色，如果已完成则标记为黑色。如果当前节点有灰色邻居，退出函数并打印“Cycle detected”

这是我的代码，带有一个简单的 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')

我认为尝试 except 会起作用，但事实并非如此。

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

标签： python-3.xrecursionexceptiondepth-first-search

解决方案

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

删除尝试，除了模式，而是将 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) 具有双重职责，打开递归调用并检索其输出。由于这个return是在最外层的递归中，并且在上述return语句之后，所以当最内层的递归返回True时，它会自动切断进一步的搜索并返回true。

推荐阅读