Breadth First Search

BFS is an extremely versatile algorithm that comes up a lot in graph problems. The key property of BFS is that it explores vertices in order of the length of their shortest path from the starting vertex. Any time you're dealing with an unwieghted graph and need to find the shortest path between two vertices, BFS is a good place to start. Its usefulness doesn't end there though; BFS can be used to find connected components, detect cycles, and more.

You can think of BFS as producing level-wise sets of vertices in a graph.

$$ L_0 = {s} $$

$$ L_i = {neighbors(v_j)\ :\ v_j\ \in L_{i\ -\ 1}\setminus L_0\ \cup L_1\ \cup\ldots\cup L_{i\ -\ 2}} $$