PineWikiBreadth-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.
