Breadth First Search

Breadth-First Search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at a selected node (often referred to as the ‘root’ in trees) and explores all of its neighboring nodes at the present depth prior to moving on to nodes at the next depth level.

Properties

• For each $i,L_i$ consists of all nodes at distance exactly $i$ edges from $s$.
• There is a path from $s$ to $t$ $⟺$ $d(t)<\infty$.

Formal Definition

BFS can be formally defined as follows:

Let the graph be G = (V, E) and the start vertex be s ∈ V.

$$L_0=\{s\},L_{k+1}=\left\{v\in V\setminus \bigcup _{i=0}^k{L}_i|\exists u\in L_k\text{ with }(u,v)\in E\right\}$$

Define the distance (in number of edges) from s:

$$d(v)=\{\begin{array}{ll}k,& \text{if }v\in L_k\\ \infty ,& \text{if }v\notin {\bigcup }_{i\ge 0}{L}_i\end{array}$$

Define a predecessor function that induces a BFS tree:

$$\pi (s)=\perp ,\pi (v)\in L_{d(v)-1}\text{ with }(\pi (v),v)\in E\text{ for }d(v)\ge 1$$

The BFS tree is:

$$T=(V_T,E_T),V_T=\{v\in V\mid d(v)<\infty \},E_T=\{(\pi (v),v)\mid v\in V_T\setminus \{s\}\}$$

Correctness (shortest-path property):

$$\forall v\in V:d(v)=\delta (s,v):=\min \{\text{length}(P)\mid P\text{ is a path }s⇝v\}$$

Complexity (with adjacency lists):

$$\text{time}=\Theta (|V|+|E|),\text{space}=\Theta (|V|)$$

Pseudocode