> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-2/graph-search/graph-theory/topological_sort/cycle-detection.md).

# 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.

```java
// 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.

```java
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](https://courses.csail.mit.edu/6.006/fall11/rec/rec14.pdf)
* GeeksforGeeks - [Detect Cycle in a Directed Graph using BFS](https://www.geeksforgeeks.org/detect-cycle-in-a-directed-graph-using-bfs/)&#x20;