Breadth-First Search

Summarized notes on Introduction to Algorithms, Chapter 22

---

• works on both directed and undirected graphs
• Given source vertex $s$, BFS systematically explores edges of $G$ to discover every vertex that is reachable from $s$
• it computes the shortest-path distance (min number of edges) from $s$ to each reachable vertex
• output of BFS is one breadth-first tree, where $s$ is root and all reachable vertices are nodes
• result of BFS depends on which order each adjacent vertexes are visited but the computed distances will be the same independent of order

Edge coloring

• all vertices start out as white
• when edge is discovered it becomes nonwhite
• grey vertices are the "frontier" - may have some adjacent white vertices
• black vertices are such that they have no undiscovered adjacent vertices
• BFS FIFO queue consists of grey vertices

Complexity

Running Time
$O(V+E)$	BFS is linear time

Breadth-First Tree

• is a predecessor subgraph such that $G_{\pi }=(V_{\pi },E_{\pi })$
• consists of vertices reachable form $s$
• contains a unique simple path from $s$ to $v$
• is connected and has |$V_{\pi }-1$| tree edges