      JOELib JOELib Tutorial Algorithms

 BFS DFS Distance matrix Geom. dist. matrix Morgan

# 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 6-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```
The time complexity is [clr98].

Last changes: 19.03.2018, 18:47 CET (UTC/GMT +1 hour) wegner.
http://www.ra.cs.uni-tuebingen.de/software/joelib/tutorial/algorithms/algorithms.html
© 2003 University of Tübingen, Germany