breadth-first search
Breadth-first search (BFS) explores a graph in rings, like ripples spreading from where a pebble hits water. Starting from one vertex, it first visits all the immediate neighbors (distance 1), then all of their unvisited neighbors (distance 2), and so on. It fans out level by level, never rushing deep into one branch before the closer vertices are done.
The engine behind this order is a queue (first in, first out). You enqueue the start vertex, then repeatedly take the front vertex out, mark it visited, and enqueue any of its neighbors you have not seen yet. The queue holds the current frontier, so vertices come out in increasing order of distance from the start. Marking vertices as visited is essential — without it, cycles would trap you in an endless loop.
BFS visits each vertex once and inspects each edge once, so on an adjacency list it runs in O(V + E) time. Its signature payoff: in an unweighted graph, the level at which BFS first reaches a vertex is its shortest distance (fewest edges) from the start. That makes BFS the go-to tool for shortest paths when every edge counts the same.
queue<int> q;
vector<bool> seen(n, false);
q.push(start); seen[start] = true;
while (!q.empty()) {
int v = q.front(); q.pop();
for (int nb : adj[v])
if (!seen[nb]) { seen[nb] = true; q.push(nb); }
}Mark visited the moment you enqueue, so a vertex is never queued twice.
BFS gives shortest paths only when edges are unweighted (or all equal). With differing weights you need Dijkstra's algorithm instead.