BFS is one of the main graph traversal algorithms. In DFS, we recursively travel as deep as possible to find paths, while in BFS we explore the graph layer by layer. We can imagine BFS as a fire spreading from the start node. Initially it is only at the start, at second 1 it spreads to all adjacent nodes to the start. In the second second, the fires spread once again to each adjacent node that hasn’t been visited. In a sense we are creating a ring of fire that expands outwards as we search the graph.
This is an illustration of how BFS works, we can sort of see how the fire spreads each second.
Due to this idea of searching layer by layer, BFS will always find the shortest path from one node to another in an unweighted graph.
| vector<bool> vis; //resize this to the number of nodes queue<int> Q; Q.push(start); vis[start] = true; while(!Q.empty()){ int v = Q.front(); Q.pop(); for(int u : adj[v]){ if(!vis[u]){ vis[u] = true; Q.push(u); //extend the ring } } } |
BFS is very useful when trying to find layer ordered traversals of graphs.