7.2. Cycle Detection

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

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

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?

• L2-3: marks the target vertex visited.

• L5: for each incoming edge of the target vertex:

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