Breadth-First Search

Overview

Bread-first search operates on a graph $G=⟨V,E⟩$ and a source vertex $s$.

To keep track of progress, BFS colors each vertex white, gray, or black. All vertices start out white. They are colored gray upon discovery. They are painted black once all edges have been explored.

Breadth-First Forests

To color an entire graph black, BFS may need to be invoked multiple times. After each invocation of BFS, a new invocation can be run with any remaining white vertex as the source. Each invocation yields a breadth-first tree. Multiple invocations yield a breadth-first forest.