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 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 like us who are used to thinking recursively—is depth-first search. 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.

$\underline{RecursiveDFS(v):} \\ \hspace{0.4cm} if\space v\space is\space unmarked \\ \hspace{1cm} mark\space v \\ \hspace{1.0cm} for\space each\space edge\space vw \\ \hspace{1.7cm} RecursiveDFS(w)$

$\underline{IterativeDFS(s):} \\ \hspace{0.4cm} Push(s) \\ \hspace{0.4cm} while\space the\space stack\space is\space not\space empty \\ \hspace{1.0cm} v ← Pop \\ \hspace{1cm} if\space v\space is\space unmarked \\ \hspace{1.7cm} mark\space v \\ \hspace{1.7cm} for\space each\space edge\space vw \\ \hspace{2.3cm} Push(w)$ ...