BFS on General Graphs

BFS (Breadth-First Search) is a graph traversal like DFS, but it explores nodes in layers based on distance from a start node.

BFS is like “visit everything 1 step away, then 2 steps away, then 3 steps away…”

What BFS is used for

BFS is the go-to tool for:

  • Shortest path in an unweighted graph (each edge cost = 1)
  • Minimum number of edges from a start node to all nodes
  • Checking connectivity / components

The key guarantee:

In an unweighted graph, BFS finds the shortest distance (fewest edges) from the start node to every reachable node.

Core idea: a queue + visited / distance

BFS uses a queue so nodes are processed in the same order they were discovered.

Maintain:

  • dist[v] = shortest number of edges from start to v (-1 means “not visited yet”)

Process:

  1. Put the start node in the queue, set dist[start] = 0

  2. Pop a node v

  3. For each neighbor to:

    • if it’s unvisited, set dist[to] = dist[v] + 1
    • push it into the queue

Because the queue processes earlier layers first, the first time you visit a node is guaranteed to be via the shortest path.

Implementation

Assume adjacency list:

int n;
vector<int> g[n];

BFS from a single source:

vector<int> dist(n, -1);
queue<int> q;

int s = 0;
dist[s] = 0;
q.push(s);

while (!q.empty()) {
    int v = q.front(); q.pop();
    for (int to : g[v]) {
        if (dist[to] != -1) continue;     // already visited
        dist[to] = dist[v] + 1;
        q.push(to);
    }
}

Now dist[v] is:

  • 0 for the start node
  • 1 for nodes one edge away
  • 2 for nodes two edges away
  • etc.
  • -1 if unreachable from s

BFS “layers” intuition (why shortest paths work)

When BFS runs:

  • the queue first contains all nodes at distance 0
  • then it grows with all nodes at distance 1
  • then all nodes at distance 2
  • …

So if to is discovered from v, the first time you set dist[to] it must be dist[v] + 1, and v is already the earliest possible layer that could reach it.

That’s why BFS gives shortest paths in unweighted graphs.

Getting the actual shortest path (not just distance)

Store parent[to] when you discover to.

vector<int> dist(n, -1), parent(n, -1);
queue<int> q;

int s = 0;
dist[s] = 0;
q.push(s);

while (!q.empty()) {
    int v = q.front(); q.pop();
    for (int to : g[v]) {
        if (dist[to] != -1) continue;
        dist[to] = dist[v] + 1;
        parent[to] = v;
        q.push(to);
    }
}

Reconstruct path from s to t:

vector<int> path;
int t = 7;
if (dist[t] != -1) {
    for (int v = t; v != -1; v = parent[v]) path.push_back(v);
    reverse(path.begin(), path.end());
}

BFS vs DFS (practical difference)

  • DFS is great for:

    • exploring structure
    • detecting cycles
    • connected components
    • topological sorting (directed acyclic graphs)

  • BFS is great for:

    • shortest paths in unweighted graphs
    • “minimum steps” problems
    • level-by-level exploration

Quick summary

  • BFS uses a queue
  • Visits nodes in increasing distance from the start
  • Gives shortest path lengths in unweighted graphs
  • With parent[], you can reconstruct the shortest path