Chapter 4. Basic Graph Algorithms
4.1 Breadth-First Search
Breadth-first search (BFS) is a fundamental technique for discovering information about a graph that can be applied to many different problems. The BGL provides a generic implementation of BFS in the
() algorithm. This function template is parameterized so that it can be used in many situations. In this section, we describe breadth-first search and show how to use BFS to calculate Bacon numbers.
Breadth-first search is a traversal through a graph that discovers all of the vertices reachable from a given source vertex. The order in which the vertices are discovered is determined by the distance from the source vertex to each vertex, with closer ...