Introduction to Depth-First Search

In this lesson, we’ll focus on a particular instantiation of the depth-first search algorithm. Primarily, we’ll look at the behavior of this algorithm in directed graphs. Although depth-first search can be accurately described as “whatever-first search with a stack,” the algorithm is normally implemented recursively rather than using an explicit stack:

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

Implementation

Explanation

• Line 1: The dfs function takes three arguments: v is the current vertex being visited, marked is the list to keep track of visited vertices, and adj is the adjacency list representation of the graph.

• Lines 2–6: Here, we represent the recursive part of the dfs function. It first marks the current vertex v as visited by setting marked[v] = True. For each adjacent vertex w, it checks if it has already been visited by checking the corresponding value in marked list. If it has not been visited yet (not marked[w]), then it calls the dfs function recursively with the adjacent vertex w as the new starting vertex.

Optimization

We can make this algorithm slightly faster (in practice) by checking whether a node is marked before we recursively explore it. This modification ensures that we call $DFS(v)$ only once for each vertex $v$. We can further modify the algorithm to compute other useful information about the vertices and edges by introducing two black-box subroutines, $PreVisit$ and $PostVisit$, which we leave unspecified for now.

$$\begin{gathered} \underset{‾}{DFS(v):} \\ markv \\ PreVisit(v) \\ foreachedgevw \\ ifwisunmarked \\ parent(w)\leftarrow v \end{gathered}$$ ...