BFS (Breadth-First Search)

Concept

BFS explores a graph level by level, visiting all neighbors of a node before moving deeper. It uses a queue to process nodes in FIFO order, guaranteeing the shortest path in unweighted graphs.

When to Use

▸Finding the shortest path in an unweighted graph
▸Checking if a node is reachable from another
▸Traversing all connected components
▸Level-order traversal (e.g., how many steps from A to B?)

Intuition

Think of dropping a stone in water — the ripples expand outward equally in all directions. BFS works the same way: it visits all nodes at distance 1 first, then distance 2, and so on. The queue ensures we always process the "oldest" discovered node first.

Complexity

Time

O(V + E)

Space

O(V)

Template Code

cpp

#include<bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);
    int node, edges;
    cin >> node >> edges;

    vector<int> adj[node];

    for(int i = 0; i < edges; i++){
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b]. push_back(a);
    }

    int start = 4;

    vector<bool> visited(node, false);
    queue<int> q;

    q.push(start);

    while(!q.empty()){
        int u = q.front();
        q.pop();

        if(visited[u]) continue;
        visited[u] = true;

        cout << u << " ";

        for(int x : adj[u]){
            if(!visited[x]){
                q.push(x);
            }
        }
    }

    return 0;
}

// Sample Input:
// 6 7
// 0 1
// 0 2
// 1 3
// 2 3
// 3 4
// 4 5
// 2 5
//
// Sample Output (starting from node 4):
// 4 3 5 1 2 0