Breadth-first search

Input: A graph G and a starting vertex root of G

Output: Goal state. The parent links trace the shortest path back to root[8]

 1  procedure BFS(G, root) is
 2      let Q be a queue
 3      label root as explored
 4      Q.enqueue(root)
 5      while Q is not empty do
 6          v := Q.dequeue()
 7          if v is the goal then
 8              return v
 9          for all edges from v to w in G.adjacentEdges(v) do
10              if w is not labeled as explored then
11                  label w as explored
12                  w.parent := v
13                  Q.enqueue(w)

Example

The following is an example of the breadth-first tree obtained by running a BFS on German cities starting from Frankfurt:

An example map of Southern Germany with some connections between cities

The breadth-first tree obtained when running BFS on the given map and starting in Frankfurt

An enumeration of the vertices of a graph is said to be a BFS ordering if it is the possible output of the application of BFS to this graph.

Let ${\displaystyle G=(V,E)}$ be a graph with ${\displaystyle n}$ vertices. Recall that ${\displaystyle N(v)}$ is the set of neighbors of ${\displaystyle v}$. Let ${\displaystyle \sigma =(v_{1},\dots ,v_{m})}$ be a list of distinct elements of ${\displaystyle V}$, for ${\displaystyle v\in V\setminus \{v_{1},\dots ,v_{m}\}}$, let ${\displaystyle \nu _{\sigma }(v)}$ be the least ${\displaystyle i}$ such that ${\displaystyle v_{i}}$ is a neighbor of ${\displaystyle v}$, if such a ${\displaystyle i}$ exists, and be ${\displaystyle \infty }$ otherwise.

Let ${\displaystyle \sigma =(v_{1},\dots ,v_{n})}$ be an enumeration of the vertices of ${\displaystyle V}$. The enumeration ${\displaystyle \sigma }$ is said to be a BFS ordering (with source ${\displaystyle v_{1}}$) if, for all ${\displaystyle 1<i\leq n}$, ${\displaystyle v_{i}}$ is the vertex ${\displaystyle w\in V\setminus \{v_{1},\dots ,v_{i-1}\}}$ such that ${\displaystyle \nu _{(v_{1},\dots ,v_{i-1})}(w)}$ is minimal. Equivalently, ${\displaystyle \sigma }$ is a BFS ordering if, for all ${\displaystyle 1\leq i<j<k\leq n}$ with ${\displaystyle v_{i}\in N(v_{k})\setminus N(v_{j})}$, there exists a neighbor ${\displaystyle v_{m}}$ of ${\displaystyle v_{j}}$ such that ${\displaystyle m<i}$.

Breadth-first search can be used to solve many problems in graph theory, for example:

• Copying garbage collection, Cheney's algorithm
• Finding the shortest path between two nodes u and v, with path length measured by number of edges (an advantage over depth-first search)[13]
• (Reverse) Cuthill–McKee mesh numbering
• Ford–Fulkerson method for computing the maximum flow in a flow network
• Serialization/Deserialization of a binary tree vs serialization in sorted order, allows the tree to be re-constructed in an efficient manner.
• Construction of the failure function of the Aho-Corasick pattern matcher.
• Testing bipartiteness of a graph.
• Implementing parallel algorithms for computing a graph's transitive closure. [14]

• Depth-first search
• Iterative deepening depth-first search
• Level structure
• Lexicographic breadth-first search
• Parallel breadth-first search

• Open Data Structures - Section 12.3.1 - Breadth-First Search, Pat Morin