Breadth First Search (BFS)

Revision en3, by Nourhan_Abo-Heba, 2026-02-10 01:17:56

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 visited when pushing to queue
  • BFS is basically multi-source Dijkstra with weight = 1

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Nourhan_Abo-Heba 2026-02-10 01:17:56 347
en2 English Nourhan_Abo-Heba 2026-02-06 06:02:47 36 Tiny change: '\n\n**BFS** ' -> '\n**BFS** '
en1 English Nourhan_Abo-Heba 2026-02-06 06:02:21 2583 Initial revision (published)