如何使用 DFS 正确检测周期？

Question

这是我用于检测图中循环的代码：

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'))

为什么总是 returns 正确？即使有循环，else 子句也不会执行。我错过了什么吗？谢谢！

Answer 1

我认为问题在于您需要 return 对 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”的检查，它 return 是错误的，但你没有对那个 returned 值做任何事情，所以顶层它退出 for 循环并且 returns 对用户来说是真的。希望这对您有所帮助！

如何使用 DFS 正确检测周期？

How to correctly detect cycle using DFS?

python

depth-first-search