bfs

Breadth-First Search

• A single FIFO queue, storing vertices at distance $k$ and then $k+1$.
• Enqueue every white vertex exactly once, blacken them when they are dequeued.
• $O(E+V)$.
• Breadth-first tree, also determines a shortest-path on unweighted graphs. Predecessor subgraph $G_{\pi }=(V_{\pi },E_{\pi })$
• Defined as starting from one source only.