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

Question

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)

Answer 1

I'd like to introduce a minor fix into Pranav Gor's answer. If I run this algorithm as given, it traverses some edges several times. The fixed version is below.

from enum import Enum

class Color(Enum):
    White = 0
    Grey  = 1
    Black = 2

class Vertex:
    def __init__(self):
        self.color = Color.White
        self.neighbors = []

N = 5
vs = list(map(lambda _: Vertex(), [None] * N))

ACCESS_COUNT = EDGE_COUNT = 0

for i in range(N):
    for j in range(N - 1, i, -1):
        vs[i].neighbors.append(j)
        EDGE_COUNT += 1

def dfs_iterative(u: int) -> bool:
    global vs, ACCESS_COUNT

    stack = []
    stack.append(u)

    while len(stack) > 0:
        u = stack[len(stack) - 1]

        if vs[u].color == Color.White:
            vs[u].color = Color.Grey
            for v in vs[u].neighbors:
                ACCESS_COUNT += 1
                print(f"{u} -> {v}")

                if vs[v].color == Color.White:
                    stack.append(v)

                elif vs[v].color == Color.Grey:
                    return False

                # == Black -> do nothing

        elif vs[u].color == Color.Grey:
            stack.pop()
            vs[u].color = Color.Black

        elif vs[u].color == Color.Black:
            stack.pop()

    return True

print(dfs_iterative(0))
print(EDGE_COUNT, ACCESS_COUNT)

P.S.: Perhaps it would be more suitable to write a comment, but I cannot due to not having 50 reputation.

Answer 2

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

Answer 3

Java version :

public class CycleDetection {
    private List<ArrayList<Integer>> adjList = new ArrayList<>();
    private boolean[] visited;

    public static void main(String[] args) {
        CycleDetection graph = new CycleDetection();
        graph.initGraph(4);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        //graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        //graph.addEdge(3, 3);
        System.out.println(graph.isCyclic());
    }

    private boolean isCyclic() {
        Stack<Integer> stack = new Stack<>();
        //DFS
        boolean[] recStack = new boolean[this.adjList.size()];
        stack.add(0);//push root node
        while (!stack.empty()) {
            int node = stack.pop();
            /*if (recStack[node]) {
                return true;
            }*/
            visited[node] = true;
            recStack[node] = true;
            List<Integer> neighbours = this.adjList.get(node);
            ListIterator<Integer> adjItr = neighbours.listIterator();
            while (adjItr.hasNext()) {
                int currentNode = adjItr.next();
                if (!visited[currentNode]) {
                    visited[currentNode] = true;
                    stack.push(currentNode);
                } else {
                    if (recStack[currentNode]) {
                        return true;
                    }
                }
            }
            if (neighbours == null || neighbours.isEmpty())
                recStack[node] = false;

        }

        return false;
    }

    private void initGraph(int nodes) {
        IntStream.range(0, nodes).forEach(i -> adjList.add(new ArrayList<>()));
        visited = new boolean[nodes];
    }

    private void addEdge(int u, int v) {
        this.adjList.get(u).add(v);
    }
}

Answer 4

I have solved this problem as a solution for this Leetcode problem - https://leetcode.com/problems/course-schedule/

I have implemented it in Java - using recursive DFS using colors, recursive DFS using visited array, iterative DFS and BFS using indegree and calculating topological sort.

class Solution {
    //prereq is the edges and numCourses is number of vertices
    public boolean canFinish(int numCourses, int[][] prereq) {

        //0 -> White, -1 -> Gray, 1 -> Black
        int [] colors = new int[numCourses];
        boolean [] v = new boolean[numCourses];
        int [] inDegree = new int[numCourses];
        Map<Integer, List<Integer>> alMap = new HashMap<>();
        
        for(int i = 0; i < prereq.length; i++){
            int s = prereq[i][0];
            int d = prereq[i][1];
            alMap.putIfAbsent(s, new ArrayList<>());
            alMap.get(s).add(d);
            inDegree[d]++;
        }
        // if(hasCycleBFS(alMap, numCourses, inDegree)){
        //     return false;
        // }
        for(int i = 0; i < numCourses; i++){
            if(hasCycleDFS1(i, alMap, colors)){
            // if(hasCycleDFS2(i, alMap, v)){
            //if(hasCycleDFSIterative(i, alMap, colors)){
                return false;
            }
       }
        return true;
    }
    //12.48
    boolean hasCycleBFS(Map<Integer, List<Integer>> alMap, int numCourses, int [] inDegree){
        //short [] v = new short[numCourses];
        Deque<Integer> q = new ArrayDeque<>();
        for(int i = 0; i < numCourses; i++){
            if(inDegree[i] == 0){
                q.offer(i);
            }
        }
        List<Integer> tSortList = new ArrayList<>();
        while(!q.isEmpty()){
            int cur = q.poll();
            tSortList.add(cur);
            //System.out.println("cur = " + cur);
            
            if(alMap.containsKey(cur)){
                for(Integer d: alMap.get(cur)){
                    //System.out.println("d = " + d);
                    // if(v[d] == true){
                    //     return true;
                    // }
                    inDegree[d]--;
                    if(inDegree[d] == 0){
                        q.offer(d);
                    }
                }
            }
        }
       
        return tSortList.size() == numCourses?  false:  true;
    }
    // inspired from - https://leetcode.com/problems/course-schedule/discuss/58730/Explained-Java-12ms-Iterative-DFS-solution-based-on-DFS-algorithm-in-CLRS
    //0 -> White, -1 -> Gray, 1 -> Black
    boolean hasCycleDFSIterative(int s, Map<Integer, List<Integer>> alMap, int [] colors){
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(s);
        while(!stack.isEmpty()){
            int cur = stack.peek();
            if(colors[cur] == 0){
                colors[cur] = -1;
                if(alMap.containsKey(cur)){
                    for(Integer d: alMap.get(cur)){
                        if(colors[d] == -1){
                            return true;
                        }
                        if(colors[d] == 0){
                            stack.push(d);
                        }
                    }
                }
            }else if (colors[cur] == -1 || colors[cur] == 1){
                    colors[cur] = 1;
                    stack.pop();
            }
        }

        return false;
    }
    
    boolean hasCycleDFS1(int s, Map<Integer, List<Integer>> alMap, int [] colors){
        // if(v[s] == true){
        //     return true;
        // }
        colors[s] = -1;
        if(alMap.containsKey(s)){
            for(Integer d: alMap.get(s)){
                //grey vertex
                if(colors[d] == -1){
                    return true;
                }
                if(colors[d] == 0 && hasCycleDFS1(d, alMap, colors)){
                    return true;
                }
            }
        }
        colors[s] = 1;
        return false;
    }
    
    // not efficient because we process black vertices again 
    boolean hasCycleDFS2(int s, Map<Integer, List<Integer>> alMap, boolean [] v){
        // if(v[s] == true){
        //     return true;
        // }
        v[s] = true;
        if(alMap.containsKey(s)){
            for(Integer d: alMap.get(s)){
                if(v[d] == true || hasCycleDFS2(d, alMap, v)){
                    return true;
 
                }
            }
        }
        v[s] = false;
        return false;
    }
    
}

Answer 5

You could do that simply by not popping the stack element right away. For every iteration, do v = stack.peek() and if v is White, mark it as Grey and go ahead exploring its neighbours.

However, if v is Grey, it means that you have encountered v for the second time in the stack and you have completed exploring it. Mark it Black and continue the loop.

Here's how your modified code should look like:

procedure DFS-iterative(G,v):
    let S be a stack
    S.push(v)
    while S is not empty
        v = S.peek()
        if v is not labeled as Grey:
            label v as Grey
            for all edges from v to w in G.adjacentEdges(v) do
                if w is labeled White do
                    S.push(w)
                elif w is labeled Grey do
                    return False    # Cycle detected
                                    # if w is black, it's already explored so ignore
        elif v is labeled as Grey:
            S.pop()                 # Remove the stack element as it has been explored
            label v as Black

If you're using a visited list to mark all visited nodes and another recStack i.e a list which keeps track of nodes currently being explored, then what you can do is, instead of popping the element from stack, just do stack.peek(). If the element is not visited (it means you're encountering that element for the first time in the stack), just mark it True in visited and recStack and explore its children.

However, if the peek() value is already visited, it means you're ending the exploration of that node so just pop it and make it's recStack as False again.

Answer 6

In DFS, end of a branch is nodes that has no children these nodes is Black. Then checked parents of these nodes. If a parent do not has Gray child then it is Black. Likewise, if you continue to set black color to nodes, color of all nodes becomes black.

For example, I want to perform DFS in graph below.

DFS starts from u and visited u -> v -> y -> x. x has no children and you should change color of this node to Black.

Then return to parent of x in visited path according to discovery time. So parent of x is y. y has no children with Gray color so you should change color of this node to Black.