Breadth-first search (BFS) is a graph traversal algorithm for unweighted graphs, where the idea is we look at all nodes at a depth before searching the nodes at a depth . It has a time complexity of .
A queue is used to keep track of the waves of vertices at a distance and distance . 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).
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