For a graph and a start vertex , the breadth-first search of from is a traversal of the graph that visits each vertex exactly once and for each edge exactly once (may not traversal all). Such traversal graph is called a breadth-first tree. Moreover, we do color each vertex as white, gray, or black. We start with as gray and all other vertices as white. We then visit each vertex exactly once and for each edge exactly once. Once all adjacent vertices of are visited, we color as black. We do this by maintaining a queue of vertices that we have discovered but not yet visited. Initially, contains only .
The total run-time of BFS is where the initialization takes time and scanning all the edges takes time.
Some problems can be solved by BFS: shortest path, connected components, bipartite, two-colorability, etc.
- shortest path: we do BFS and return the degree of the target node. If we can successfully reach the target node, we will update the degree of the target node. Otherwise, we will see its degree is infinity which is the default value.
For a graph and a start vertex , we define predecessor subgraph of from where such that and . Such subgraph is breath-first tree if contains all reachable vertices from and there is a unique path from to in (also is the shortest path from to ).
The BFS algorithm take time.
We also define the shortest-path distance from to in as the length of the shortest path from to in .