> For the complete documentation index, see [llms.txt](https://emory.gitbook.io/dsa-java/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emory.gitbook.io/dsa-java/graphs/cycle-detection.md).

# 7.2. Cycle Detection

A cycle in a graph can be detected by traversing through the graph:

{% embed url="<https://www.slideshare.net/jchoi7s/cycle-detection>" %}

Let us define the `containsCycle()` method under the `Graph` class that returns true if the graph contains any cycle; otherwise, false:

```java
public boolean containsCycle() {
    Deque<Integer> notVisited = IntStream.range(0, size()).boxed().collect(Collectors.toCollection(ArrayDeque::new));

    while (!notVisited.isEmpty()) {
        if (containsCycleAux(notVisited.poll(), notVisited, new HashSet<>()))
            return true;
    }

    return false;
}
```

* `L2`: initially all vertices are not visited.
* `L4`: iterates until all vertices are visitied:
  * `L5-6`: if the recursive call finds a cycle, returns `true`.

> What is the worst-case complexity of the `containsCycle()` method?

```java
private boolean containsCycleAux(int target, Deque<Integer> notVisited, Set<Integer> visited) {
    notVisited.remove(target);
    visited.add(target);

    for (Edge edge : getIncomingEdges(target)) {
        if (visited.contains(edge.getSource()))
            return true;

        if (containsCycleAux(edge.getSource(), notVisited, new HashSet<>(visited)))
            return true;
    }

    return false;
}
```

* `L2-3`: marks the target vertex visited.
* `L5`: for each incoming edge of the target vertex:
  * `L6-7`: returns true if the source vertex of this edge has seen before.
  * `L9-10`: returns true if the recursive call finds a cycle.

> Why do we need to pass the new `HashSet` for every call in `L5`?