7.2. Cycle Detection

This section describes an algorithm to detect a cycle in a graph.

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?

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?