Depth-first search (DFS) traverses a graph by following one path as far as possible, then backtracking to try another available edge. Unlike breadth-first search (BFS), it does not explore outward in distance-based rings and cannot find shortest paths. section 13.14 section 13.16
DFS supports several graph-analysis tasks:
- Checking whether a graph contains cycles. section 13.14
- Finding connected and strongly connected components. section 13.14
- Finding a topological ordering for directed acyclic graphs. section 13.14
Detecting cycles with vertex colors
Mark every vertex white initially. When DFS visits a vertex, mark it gray, push its outgoing neighbors, and later mark it black after those edges are explored. Encountering a gray vertex indicates 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
An iterative Python implementation uses a stack of vertices and return markers, tracks white, gray, and black states, and reports whether the graph is acyclic. section 13.14
