Another algorithm that can be build on top of depth-first search is a “cycle detection”. A cycle in a graph is a path that starts and ends at the same vertex. For example, in the graph below, we can start at 1 and navigate through the path 1 -> 2 -> 6 -> 5 -> 1 back to vertex 1.
We can detect a cycle in a graph by doing a series of depth-first searches. We will start from the first vertex and explore from there. As we recurse into a particular vertex, we mark it as “on the stack”. When we finish a recursive call, we unmark it as “on the stack”. If we ever encounter a vertex that is already on the stack, we have found a cycle.
When this first depth-first search is complete, we will start a new depth-first search from the first vertex that was not yet visited. We continue this process until all vertices have been visited.
DetectCycle(graph):
Set visitedSet
for each vertex in graph:
if not visitedSet.contains(vertex):
// start a depth-first search from vertex
Set onStack
if doDFSCycle(graph, vertex, visitedSet, onStack):
return true // found a cycle
return false // no cycle found
doDFSCycle(graph, vertex, visitedSet, onStack):
if onStack.contains(vertex):
return true // found a cycle
if visitedSet.contains(vertex):
return false // already visited, but not on the current path
visitedSet.add(vertex)
onStack.add(vertex) // this is on the path we are currently exploring
for each neighbor in graph.getNeighbors(vertex):
if doDFSCycle(graph, neighbor, visitedSet, onStack):
return true // found a cycle through this neighbor
onStack.remove(vertex) // done exploring through this vertex
return false
Again, doDFSCycle looks very similar to the base DFS algorithm from Listing 34.7.3. The key differences this time are:
We keep track of what is “on the stack” in addition to what is “visited”.
The animation will load a specific graph and start a depth-first search from vertex 0. Step through the animation. As you do so, note how the OnStack tables is updated.
You can click and drag on the animation area to pan around. Use the Ctrl + mouse wheel (or touchpad scroll gesture) while over the animation area to zoom in and out.
