4.1.2. Breadth-First Search

Breadth-First Search

Breadth-First Search (BFS) is a graph traversal algorithm that expands the shallowest frontier node first, using a FIFO queue, breaking ties by selecting the leftmost branch.

It is complete because it will eventually reach the shallowest goal node, and it is optimal only when all edge costs are equal. Its time complexity is $O(b^s)$, where $s$ is the level of the shallowest solution, and its space complexity is also $O(b^s)$ . The following is a representation of BFS on a 3-level 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: Visit B (queue order after A: B, C) ---
\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: Visit C ---
\begin{scope}[animate = {myself:: = {:visible = {0s="false", 2s="true", 3s="false", 7s="false", repeats}}}]
 \foreach \n in {A,B} { \fill[orange, opacity=.25] (\n) circle (\rvis); }
 \draw[orange, opacity=.6, line width=1pt] (A) -- (C);
 \fill[teal, opacity=.35] (C) circle (\rvis);
\end{scope}
 
% --- Step 3: Visit D (children of B first) ---
\begin{scope}[animate = {myself:: = {:visible = {0s="false", 3s="true", 4s="false", 7s="false", repeats}}}]
 \foreach \n in {A,B,C} { \fill[orange, opacity=.25] (\n) circle (\rvis); }
 \draw[orange, opacity=.6, line width=1pt] (B) -- (D);
 \fill[teal, opacity=.35] (D) circle (\rvis);
\end{scope}
 
% --- Step 4: Visit E (next child of B) ---
\begin{scope}[animate = {myself:: = {:visible = {0s="false", 4s="true", 5s="false", 7s="false", repeats}}}]
 \foreach \n in {A,B,C,D} { \fill[orange, opacity=.25] (\n) circle (\rvis); }
 \draw[orange, opacity=.6, line width=1pt] (B) -- (E);
 \fill[teal, opacity=.35] (E) circle (\rvis);
\end{scope}
 
% --- Step 5: Visit F (child of C) ---
\begin{scope}[animate = {myself:: = {:visible = {0s="false", 5s="true", 6s="false", 7s="false", repeats}}}]
 \foreach \n in {A,B,C,D,E} { \fill[orange, opacity=.25] (\n) circle (\rvis); }
 \draw[orange, opacity=.6, line width=1pt] (C) -- (F);
 \fill[teal, opacity=.35] (F) circle (\rvis);
\end{scope}
 
% --- Step 6: Done (show all visited and edges) ---
\begin{scope}[animate = {myself:: = {:visible = {0s="false", 6s="true", 7s="false", repeats}}}]
 \foreach \n in {A,B,C,D,E,F} { \fill[orange, opacity=.25] (\n) circle (\rvis); }
 \draw[orange, opacity=.6, line width=1pt] (A) -- (B);
 \draw[orange, opacity=.6, line width=1pt] (A) -- (C);
 \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] (C) -- (F);
\end{scope}
 
\end{tikzpicture}
\end{document}

Proof

We now prove the time and space complexity of BFS.

• Time Complexity. Consider a tree with $m$ tiers/levels, such that the maximum branching factor of any node is $b$. Let the goal node be on level $s\le m$. Then, the worst-case scenario occurs when the goal is the last expanded node on level $s$. Since we truncate the tree to account for the solution on level $s$, there are $1+b+b^2+\dots +b^s=\frac{b^{s+1}-1}{b-1}$ nodes to be searched in this truncated tree. This means that the time complexity is $O(b^s)$.
• Space Complexity. Consider the same tree as above. BFS needs to store all nodes at the current level, plus their children (i.e., the nodes on the next level). As such, the space complexity is $O(b^s+b^{s+1})=O(b^s)$.

Implementation