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 breadth_first_search() 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.

4.1.1 Definitions

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 ...

Get The Boost Graph Library: User Guide and Reference Manual now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.