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.

CategoryAlgorithmNotes CategoryProgrammingNotes