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