Breadth-First Search (BFS)

Explore in rings

BFS visits the start, then all its neighbours, then theirs... in growing rings, using a queue. The first time it reaches a vertex is along a shortest path (fewest edges).

Think of it like this: Ripples from a stone dropped in a pond reach close points first.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    //  0 - 1 - 3 - 5
    //  |       |
    //  2 - 4 --+
    int n = 6;
    vector<vector<int>> g(n);
    for (auto [a, b] : vector<pair<int, int>>{{0, 1}, {0, 2}, {1, 3}, {2, 4}, {3, 5}, {4, 3}}) {
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector<int> dist(n, -1), parent(n, -1);
    queue<int> q;
    dist[0] = 0;
    q.push(0);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int w : g[v]) {
            if (dist[w] == -1) {              // not visited yet
                dist[w] = dist[v] + 1;
                parent[w] = v;
                q.push(w);
            }
        }
    }
    for (int v = 0; v < n; v++) cout << "dist[" << v << "] = " << dist[v] << endl;

    cout << "path to 5:";
    vector<int> path;
    for (int v = 5; v != -1; v = parent[v]) path.push_back(v);
    for (int i = (int)path.size() - 1; i >= 0; i--) cout << ' ' << path[i];
    cout << endl;
    return 0;
}

Output

dist[0] = 0
dist[1] = 1
dist[2] = 1
dist[3] = 2
dist[4] = 2
dist[5] = 3
path to 5: 0 1 3 5

Every vertex and edge is handled once: O(V + E).

Common mistake: Mark a vertex as visited when you push it, not when you pop it – otherwise it can be pushed many times.