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 mark[v] = false:
- u = pop(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.