使用迭代堆栈方法检测有向图中的循环

Question

这是我试过的：

VISITED = 1
UNVISITED = -1
VISITING = 0


def dfs(g, start, num):
    
    state = {}
    for i in range(num):
        state[i] = UNVISITED
    
    
    stack = [start]
    while(stack != []):
        node = stack.pop()
        
        if(state[node] == VISITED):
            continue

        state[node] = VISITING
        
        if(node in g):
            for i in g[node]:
                stack.append(i)
                if(state[i] == VISITED):
                    return True
                
        state[node] = VISITED
 
def detect_cycle(n, edges):
        
    g = {}
    # adjacency list
    for (x, y) in edges:
        g[x] = g.get(x, []) + [y]

    for i in range(n):
        if(i in g):
            if(dfs(g, i, n) == True):
                return True   
    return False   
            
print(detect_cycle(5, [[1,4],[2,4],[3,1],[3,2]])) # outputs True (should be false)

图表图像：

上面的示例 edges = [[1,4],[2,4],[3,1],[3,2]] 不包含循环，但 returns True。所以我的算法不适用于这种情况。

我正在尝试使用着色图检测循环算法，但我不确定如何在没有递归的情况下做到这一点。

我尝试遵循但迭代的算法：Detecting a cycle in a directed graph using DFS?

Answer 1

如果访问节点（灰色）遇到与另一个访问节点的边，则检测到循环。我在初始代码中遇到的问题是无法以回溯方式设置节点 VISITED（黑色）。新代码现在有 ENTER = 0 和 EXIT = 1。Enter = 0 意味着它是我第一次访问该节点，我将它设置为灰色（访问）我第二次访问节点出口将是 1，所以我可以设置它变黑（完全访问）。

WHITE = 0
GRAY = 1
BLACK = 2

ENTER = 0
EXIT = 1


def dfs(graph, start, n):
    
    state = {}
    for i in range(n):
        state[i] = WHITE

    stack = [(start, ENTER)]
    while(stack != []):
        node, pos = stack.pop()
        
        if(pos == EXIT):
            state[node] = BLACK
            continue
        
        state[node] = GRAY
        stack.append((node, EXIT))
        
        if(node in graph):
            for v in graph[node]:
                if state[v] == GRAY:
                    return True
                elif(state[v] == WHITE):
                    stack.append((v, ENTER))
    return False
  
def detect_cycle(n, edges):
        
    g = {}
    for (x, y) in edges:
        g[x] = g.get(x, []) + [y]

    for i in range(n):
        
        if(i in g):
            if(dfs(g, i, n) == True):
                return True
            
    return False

使用迭代堆栈方法检测有向图中的循环

Detect cycle in a directed graph using iterative stack approach

python

graph