Cycle Detection

Intro

Cycle detection is naturally associated with DFS. Using BFS is just unnatural since it doesn't keep track of visited but unfinished nodes on stack and is hard to keep a parent pointer.

Detect Cycle in Directed Graph

For directed graph, a cycle exists when there's a back edge in the DFS tree.

// return true if cycle is detected, false if the graph acyclic
boolean cycleDFS(Map<Integer, List<Integer>> graph, Integer visit, 
                 Set<Integer> visited, Set<Integer> onStack) {
    // previsit
    visited.add(visit);
    onStack.add(visit);
    // visit each neighbor
    for (Integer neighbor : graph.get(visit)) {
        if (!visited.contains(neighbor) && 
            cycleDFS(graph, neighbor, visited, onStack)) {
            return true;
        } else if (onStack.contains(neighbor)) {
            // back edge
            return true;
        } else {
            // cross or forward
            // do nothing
        }
    }
    // postvisit
    onStack.remove(visit);
    return false;
}

Why we can't just return cycleDFS(graph, neighbor, visited, onStack)? We have to keep in mind what happens when the program backtracks. It will return false when it reaches the end of a path, we don't want to return false just yet. We want to return false at the root level. Therefore we have to "use" the boolean return value somewhere.

Detect Cycle in Undirected Graph

For undirected graph, a cycle exists when a node's neighbor is already visited and is not its parent.

boolean cycleDFS2(Map<Integer, List<Integer>> graph, Integer visit, 
                  Integer parent, Set<Integer> visited) {
    visited.add(visit);
    for (Integer neighbor : graph.get(visit)) { 
        if (visited.contains(neighbor) && !neighbor.equals(parent)) {
            return true;
        }
        if (!visited.contains(neighbor) && 
            cycleDFS2(graph, neighbor, visit, visited)) {
            return true;
        }
    }
    return false;
}

Note: neighbor != parent won't work here because they are two references to the Integer object. We want to compare the value not the reference ◟ʕ´∀`ʔ◞

Reference

• MIT 6.006 - Recitation 14 DFS Edge Classification

• GeeksforGeeks - Detect Cycle in a Directed Graph using BFS