Whatever-First Search

Depth-first search

So far, we have only discussed local operations on graphs; arguably, the most fundamental global question we can ask about graphs is about its reachability. Given a graph $G$ and a vertex $s$ in $G$, the reachability question asks which vertices are reachable from $s$; that is, for which vertices $v$ is there a path from $s$ to $v$? For now, let’s consider only undirected graphs; we’ll consider directed graphs briefly at the end of this section. For undirected graphs, the vertices reachable from $s$ are precisely the vertices in the same component as $s$.

Perhaps the most natural reachability algorithm—at least for people who are used to thinking recursively—is depth-first search (DFS). This algorithm can be written either recursively or iteratively. It’s exactly the same algorithm either way; the only difference is that we can actually see the “recursion” stack in the non-recursive version.