Breadth First Search

Definition

Breadth-first search (BFS) visits the nodes in increasing order of their distance from the starting node. Thus, we can calculate the distance from the starting node to all other nodes using breadth-first search. However, breadth-first search is more difficult to implement than depth-first search. Breadth-first search goes through the nodes one level after another. First the search explores the nodes whose distance from the starting node is 1, then the nodes whose distance is 2, and so on. This process continues until all nodes have been visited.

BFS is queue based.

Idea

1. Start at vertex s
2. Find all vertices 1 away from s
3. Find all vertices 1 away from the last layer
4. Repeat until all nodes have been reached

procedure bfs(G, s)  
Input: a graph G = (V, E) (directed or undirected) and a start vertex s in V
Output: For all u reachable from s, dist(u) is set to the distance from s to u  
	for all u in V :  
		dist(u) = inf
	dist(s) = 0  
	Q = [s]
	while Q is not empty:
		u = eject(Q)  
		for all edges (u, v) → E :  
			if dist(v) = inf:  
			inject(Q, v)
			dist(v) = dist(u) + 1

In BFS, we use $dist(v)$ to determine if we have reached v since it will be infinity if we have not. We can prove the correctness of BFS by induction.

The runtime here is $O(V+E)$ which is the same as in Depth First Search.