# Whatever-First Search

Understand the different techniques used to implement breadth-first search and depth-first search algorithms.

## We'll cover the following

## 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.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy