Electronic Design Automation

4.3.3. Breadth-first search and depth-first search

Many graph algorithms rely on efficient and systematic traversals of vertices and edges in the graph. The two simplest and most commonly used traversal methods are breadth-first search and depth-first search, which form the basis for many graph algorithms. We will examine their generic structures and point out some important applications.

4.3.3.1. Breadth-first search

Breadth-first search (BFS) is a systematic means of visiting vertices and edges in a graph. Given a graph G and a specific source vertex s, the BFS searches through those vertices adjacent to s, then searches the vertices adjacent to those vertices, and so on. The routine stops when BFS has visited all vertices that are reachable ...