Breadth First Search (BFS)
The BFS method performs a breadth-first search [clr98] of a graph. A breadth-first search visits vertices that are closer to the source before visiting vertices that are further away. In this context `distance' is defined as the number of edges in the shortest path from the source vertex.
Figure 1. Pseudocode for the BFS algorithm
paint all vertices white; paint the source grey, set its distance to 0 and enqueue it; repeat dequeue vertex v; if v is the target, we're done - exit this algorithm; paint v black; for each white neighbor w of v paint w grey; set distance w to (distance v + 1); set parent w to v; enqueue w until the queue is empty if we haven't yet exited, we didn't find the target
[clr98].