A cycle is a path in a graph that starts and ends at the same vertex. Following its edges eventually brings you back to where you began. section 13.5
Recognize cycles by checking these related ideas:
- A path is an ordered sequence of connected edges that lets you travel from one vertex to another. section 13.5
- A graph with at least one cycle is cyclic; a graph with no cycles is acyclic. section 13.16 section 13.5
- A loop is a special edge whose source and destination are the same vertex; it is distinct from a longer cycle. section 13.2
- Trees are acyclic graphs, so no path from a tree's root to a leaf visits the same node twice. section 11.2
A follower cycle
Suppose Giraffe follows Crocodile, Crocodile follows Monkey, and Monkey follows Giraffe. The path Giraffe→Crocodile→Monkey→Giraffe returns to its starting vertex, so it forms a cycle. Monkey↔Giraffe also forms a smaller cycle. section 13.5
Depth-first search can detect cycles in a directed graph. Mark unvisited vertices white, active vertices gray, and completed vertices black. Discovering a gray vertex means the search has reached a vertex still on the current path, revealing a cycle. section 13.14
def dfs(self, start_vertex, color=None):
if color is None:
color = {v: 'white' for v in self._adj}
acyclic = True
stack = Stack()
stack.push((False, start_vertex))
while not stack.is_empty():
(mark_as_black, v) = stack.pop()
col = color.get(v, 'white')
if mark_as_black:
color[v] = 'black'
elif col == 'grey':
acyclic = False
elif col == 'white':
color[v] = 'grey'
stack.push((True, v))
for (_, w) in self._get_vertex(v).outgoing_edges():
stack.push((False, w))
return acyclic, color
Inspect an iterative DFS implementation that uses a stack, gray and black colors, and an acyclic result. section 13.14
