BFS is one of the most important graph algorithms, especially when we want to find the shortest path in an unweighted graph.
Why BFS?
- DFS is not suitable for shortest path problems because it may go deep into one branch until reaching a leaf, even if a shorter path exists.
- BFS explores the graph level by level, which guarantees that the first time we reach a node, we reached it using the minimum number of edges.
How BFS works
- We use a queue
- Start from the source node
- Visit all neighbors (level 1)
- Then neighbors of neighbors (level 2), and so on
Queue order example:
X
x1 x2
x11 x12 x21 x22
x111 x112 x221 x222 ...
This level-by-level traversal is exactly why BFS gives the shortest path.
Key Idea for Shortest Path
- Store
(node, distance) - When we reach the destination node for the first time, that distance is the shortest path.
BFS Implementation
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
vector<int> adj[N];
bool vis[N];
int bfs(int start, int end) {
queue<pair<int,int>> q;
q.push({start, 0});
vis[start] = true;
while (!q.empty()) {
auto [node, dist] = q.front();
q.pop();
if (node == end)
return dist;
for (int nxt : adj[node]) {
if (!vis[nxt]) {
vis[nxt] = true;
q.push({nxt, dist + 1});
}
}
}
return -1; // no path
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
cout << bfs(1, 5);
}
Complexity
- Time:
O(n + m) - Space:
O(n)
Final Notes (Blog Style Tips)
- BFS = shortest path in unweighted graphs
- DFS = exploring paths, not shortest
- Always mark
visitedwhen pushing to queue - BFS is basically multi-source Dijkstra with weight = 1




