4.1.2. Depth-First Search

Depth-First Search

Depth-First Search (DFS) is an acyclic graph traversal algorithm that always expands the deepest frontier node first, implemented with a LIFO stack such that ties are broken by choosing the leftmost branch.

DFX is not complete, since cycles can lead to infinite search, and not optimal, as it simply finds the leftmost solution without considering path cost. Its time complexity is $O(b^m)$, where $m$ is the maximum level of the graph, and space complexity is $O(bm)$.

The following is a representation of DFS on a 3-tier graph.

\usetikzlibrary{trees,animations}
 
\begin{document}
\begin{tikzpicture}[
 level 1/.style={sibling distance=28mm, level distance=14mm},
 level 2/.style={sibling distance=18mm, level distance=14mm},
 nodestyle/.style={draw, circle, inner sep=2pt, minimum size=6mm},
 edgestyle/.style={}
]
 
% --- Static tree (always visible) ---
\node[nodestyle, name=A] {A}
 child { node[nodestyle, name=B] {B}
   child { node[nodestyle, name=D] {D} }
   child { node[nodestyle, name=E] {E} }
 }
 child { node[nodestyle, name=C] {C}
   child { node[nodestyle, name=F] {F} }
 };
 
% Convenience radii
\def\rvis{4mm}
 
% --- Step 0: Start at A ---
\begin{scope}[animate = {myself:: = {:visible = {0s="true", 1s="false", 7s="false", repeats}}}]
 \fill[teal, opacity=.35] (A) circle (\rvis);
\end{scope}
 
% --- Step 1: Go to B ---
\begin{scope}[animate = {myself:: = {:visible = {0s="false", 1s="true", 2s="false", 7s="false", repeats}}}]
 \fill[orange, opacity=.25] (A) circle (\rvis);
 \draw[orange, opacity=.6, line width=1pt] (A) -- (B);
 \fill[teal, opacity=.35] (B) circle (\rvis);
\end{scope}
 
% --- Step 2: Go to D ---
\begin{scope}[animate = {myself:: = {:visible = {0s="false", 2s="true", 3s="false", 7s="false", repeats}}}]
 \fill[orange, opacity=.25] (A) circle (\rvis);
 \fill[orange, opacity=.25] (B) circle (\rvis);
 \draw[orange, opacity=.6, line width=1pt] (A) -- (B) -- (D);
 \fill[teal, opacity=.35] (D) circle (\rvis);
\end{scope}
 
% --- Step 3: Backtrack to B, then visit E ---
\begin{scope}[animate = {myself:: = {:visible = {0s="false", 3s="true", 4s="false", 7s="false", repeats}}}]
 \fill[orange, opacity=.25] (A) circle (\rvis);
 \fill[orange, opacity=.25] (B) circle (\rvis);
 \fill[orange, opacity=.25] (D) circle (\rvis);
 \draw[orange, opacity=.6, line width=1pt] (A) -- (B) -- (E);
 \fill[teal, opacity=.35] (E) circle (\rvis);
\end{scope}
 
% --- Step 4: Backtrack to A, then go to C ---
\begin{scope}[animate = {myself:: = {:visible = {0s="false", 4s="true", 5s="false", 7s="false", repeats}}}]
 \fill[orange, opacity=.25] (A) circle (\rvis);
 \fill[orange, opacity=.25] (B) circle (\rvis);
 \fill[orange, opacity=.25] (D) circle (\rvis);
 \fill[orange, opacity=.25] (E) circle (\rvis);
 \draw[orange, opacity=.6, line width=1pt] (A) -- (C);
 \fill[teal, opacity=.35] (C) circle (\rvis);
\end{scope}
 
% --- Step 5: Go to F (goal/leaf) ---
\begin{scope}[animate = {myself:: = {:visible = {0s="false", 5s="true", 6s="false", 7s="false", repeats}}}]
 \foreach \n in {A,B,D,E,C} { \fill[orange, opacity=.25] (\n) circle (\rvis); }
 \draw[orange, opacity=.6, line width=1pt] (A) -- (C) -- (F);
 \fill[teal, opacity=.35] (F) circle (\rvis);
\end{scope}
 
% --- Step 6: Done (show all visited) ---
\begin{scope}[animate = {myself:: = {:visible = {0s="false", 6s="true", 7s="false", repeats}}}]
 \foreach \n in {A,B,D,E,C,F} { \fill[orange, opacity=.25] (\n) circle (\rvis); }
 \draw[orange, opacity=.6, line width=1pt] (A) -- (B);
 \draw[orange, opacity=.6, line width=1pt] (B) -- (D);
 \draw[orange, opacity=.6, line width=1pt] (B) -- (E);
 \draw[orange, opacity=.6, line width=1pt] (A) -- (C);
 \draw[orange, opacity=.6, line width=1pt] (C) -- (F);
\end{scope}
 
 
\end{tikzpicture}
\end{document}

Proof

We now prove the time and space complexity of DFS.

• Time Complexity. Consider a tree with $m$ tiers/levels, such that the maximum branching factor of any node is $b$. Since the worst-case scenario occurs when the tree is perfectly full with $1+b+b^2+\dots +b^m=\frac{b^{m+1}-1}{b-1}$, and since the $b^m$ term dominates the geometric sum as $m$ grows large, then the time complexity is $O(b^m)$.
• Space Complexity. Consider the same tree as above. DFS goes down one path at a time, so it must only remember that path and the unexplored siblings. In the worst case, that is $b$ nodes at each of the $m$ levels on the frontier when starting at the root. As such, the space complexity is $O(bm)$.

Implementation