Python 中图形实现中的循环检测

Question

我正在尝试在 python 中实现循环检测器。本质上，该算法应用 BFS 并将每个节点标记为 -1（未访问）0（正在工作）或 1（已访问）。我的算法扫描邻居，如果邻居的状态为 0，则检测到一个循环。

# this is a non-directed graph in nature
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': [],
    'D': ['B', 'E'],
    'E': ['B', 'D']
}

# 1 means visited 0 means in queue and -1 means not touched yet

status = {node: -1 for node in graph}

start = 'A'
queue = [start]
cycle = False
    
def traversal(graph): 
    start = queue.pop(-1)
    for node in graph[start]:
        if status[node] == -1:
            queue.append(node)
            status[node] = 0
        if status[node] == 0:
            cycle = True
    if queue:
        status[start] = 1
        traversal(graph)

traversal(graph)
print(cycle)

我似乎找不到代码的问题。有人可以指出吗？

Answer 1

在您的 traversal 函数中，cycle 变量是本地变量。所以

cycle = True

将 local 变量 cycle 设置为 True，对 global cycle 没有影响]变量。

return 来自函数的值

def traversal(graph): 
    cycle = False
    ... # the original function
    return cycle

cycle = traversal(graph)
print(cycle)

或将 cycle 变量标记为全局变量

cycle = False # global variable here
def traversal(graph): 
    global cycle
    ... # the original function

traversal(graph)
print(cycle)

Python 中图形实现中的循环检测

Cycle Detection in Graph Implementation in Python

python

breadth-first-search