Breadth-first search

Breadth-first search (BFS) is a graph traversal algorithm for unweighted graphs, where the idea is we look at all nodes at a depth $d$ before searching the nodes at a depth $d+1$. It has a time complexity of $\mathcal{O}(V+E)$.

A queue is used to keep track of the waves of vertices at a distance $k$ and distance $k+1$ (i.e., the frontier). Additionally, to make sure we don’t re-traverse nodes in cyclic graphs, we need to keep track of nodes that we’ve already visited (with a structure of Booleans or within the graph itself).

Nodes have three states. White (not reachable from the current node), grey (when a node is discovered, i.e., encountered for the first time during the search). The queue will contain all grey vertices; once they’re all explored, the vertex is behind the search’s frontier and it goes to black (fully searched).

Analysis

BFS will expand all nodes above the shallowest solution. The worst case time complexity is given by $\mathcal{O}(b^{d+1})$, where $d$ is the goal node depth. It is dominated by needing to add $\mathcal{O}(b)$ nodes to the frontier for every node in $\mathcal{O}(b^d)$ level. The space complexity is thus the total number of nodes on depth $d+1$, so $\mathcal{O}(b^{d+1})$.

Assuming that $b$ and $d$ is finite, then BFS is a complete algorithm. It doesn’t produce cost optimal solutions, but it does produce length optimal solutions.

Competitive programming

Standard stuff. Implementation-wise, here’s some things to remember:

• If possible, encode the state in the graph. This might mean changing the value of the node to a visited or unreachable value.
  • Before the loop, add the entrance node.
  • While checking for neighbours, change them before they’re visited by the algorithm. i.e., when they’re discovered, enqueue them and mark them as visited.

See also

• Depth-first search, the opposite traversal algorithm
• Dijkstra’s algorithm, which generalises BFS to weighted graphs