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, returnstrue
.
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 inL5
?
Last updated
Was this helpful?