Breadth-first search visits every reachable node in a graph in order of increasing distance from the starting node. It can be thought of as a ShortestPath algorithm for the special case where all edges have length 1.

Typical code for breadth-first-search:

BFS(G, s): Q = an empty queue mark[] = array of booleans, one per vertex, initially false mark[s] = true push(s, Q) while Q is not empty: u = pop(Q) DoSomethingTo(u) for each successor v of u: if mark[v] = false: push(v, Q)

If the queue is replaced by a stack, the algorithm becomes DepthFirstSearch. For a combined implementation of both breadth-first and depth-first search in C, see C/Graphs.

For distributed algorithms, see DistributedBreadthFirstSearch.