algorithmgraph-algorithmdepth-first-search

How to detect cycles in a directed graph using the iterative version of DFS?


In the recursive DFS, we can detect a cycle by coloring the nodes as WHITE, GRAY and BLACK as explained here.

A cycle exists if a GRAY node is encountered during the DFS search.

My question is: When do I mark the nodes as GRAY and BLACK in this iterative version of DFS? (from Wikipedia)

    1  procedure DFS-iterative(G,v):
    2      let S be a stack
    3      S.push(v)
    4      while S is not empty
    5          v = S.pop()
    6          if v is not labeled as discovered:
    7              label v as discovered
    8              for all edges from v to w in G.adjacentEdges(v) do 
    9                  S.push(w)

Solution

  • One option is to push each node twice to the stack along the information if you're entering or exiting it. When you pop a node from stack you check if you're entering or exiting. In case of enter color it gray, push it to stack again and advance to neighbors. In case of exit just color it black.

    Here's a short Python demo which detects a cycle in a simple graph:

    from collections import defaultdict
        
    WHITE = 0
    GRAY = 1
    BLACK = 2
        
    EDGES = [(0, 1), (1, 2), (0, 2), (2, 3), (3, 0)]
        
    ENTER = 0
    EXIT = 1
        
    def create_graph(edges):
        graph = defaultdict(list)
        for x, y in edges:
            graph[x].append(y)
        
        return graph
        
    def dfs_iter(graph, start):
        state = {v: WHITE for v in graph}
        stack = [(ENTER, start)]
        
        while stack:
            act, v = stack.pop()
        
            if act == EXIT:
                print('Exit', v)
                state[v] = BLACK
            else:
                print('Enter', v)
                state[v] = GRAY
                stack.append((EXIT, v))
                for n in graph[v]:
                    if state[n] == GRAY:
                        print('Found cycle at', n)
                    elif state[n] == WHITE:
                        stack.append((ENTER, n))
        
    graph = create_graph(EDGES)
    dfs_iter(graph, 0)
    

    Output:

    Enter 0
    Enter 2
    Enter 3
    Found cycle at 0
    Exit 3
    Exit 2
    Enter 1
    Exit 1
    Exit 0