Breadth-First Search: Finding the Shortest Path One Ripple at a Time

You look up a new colleague, and next to their name your network app prints a tiny "2nd." One person — exactly one — stands between the two of you, and the app found that shortest chain out of a graph with a billion people, in the blink it took the page to load. It didn’t try every possible chain of friends. It spread outward from you in rings — everyone one handshake away, then everyone two handshakes away — and stopped the instant a ring touched them.

That spreading has a name. It’s breadth-first search — BFS — and it’s the algorithm that answers "how far apart are these two things?" on any network where every step counts the same. By the end of this article you and I will have built it together, and gone deep on the one fact that makes it magical: the very first time BFS reaches a node, it has already found the shortest way there.

Let’s start nowhere near a computer

Forget graphs for a moment. Picture a single juicy piece of gossip and a crowded office.

At 9:00 you hear it. You immediately turn and tell the two people at your desk cluster — that’s everyone one handshake from you. A minute later, each of them turns and tells the people beside them — friends-of-friends, two handshakes out. The news pushes outward like a ripple on a pond, a whole ring at a time, until it’s reached the far corner of the floor.

Now watch three things happen in that room, because they are the algorithm.

• There’s a line of people waiting to spread it. When you hear the gossip you don’t sprint around the whole office — you tell your immediate neighbours and add them to a mental "still need to pass it on" line. Each person, when their turn comes, tells their neighbours and joins them to the back of that line. First to hear, first to spread: the line is a queue.
• Nobody bothers re-telling someone who already knows. The moment a person hears it, they’re marked "already told" and skipped forever after. That’s the visited set, and without it the gossip would echo around forever.
• The rings never overtake each other. Everyone one handshake away hears it before anyone two handshakes away, simply because the near ring finishes spreading before the far ring begins. So the number of the ring a person is in — 0, 1, 2, 3 — is exactly the length of the shortest chain of tellings that could have reached them.

That last one is the whole prize. Hold onto it: the ring you land in is your shortest distance from the source. Everything below is just that office, written down carefully.

Where you already meet it

Once you see "spread outward a ring at a time," it’s everywhere something needs the fewest steps:

• Social degrees of separation. The "2nd" beside a name, the "6 degrees" party game — fewest intermediaries between two people.
• A maze or a game board. The shortest number of moves to get from a start square to a goal; a chess knight’s fewest hops between two squares.
• Peer-to-peer and network broadcast. Flooding a message to every reachable machine, or measuring hop-count between routers.
• Image tools. The "bucket fill" in a paint app floods a region of same-coloured pixels outward from where you clicked — a BFS over the grid.

But the cleanest way to feel what BFS guarantees is a plain road map where every road is one block long. Ask "what’s the shortest drive from home to the stadium?" and, because every edge costs the same, "shortest" just means "fewest roads." BFS answers it by fanning out from home: all corners one block away, then two, then three, and the first time the fan reaches the stadium, you’ve got the answer — no distances to add up, no roads to weigh against each other.

What it actually looks like

Let’s pin down the graph we’ll use for the rest of the build. Eight nodes, a source S, and every node shaded by its distance from S.

Read it left to right, because the columns are the rings from the office. S sits alone at distance 0. Its direct neighbours B and C are the distance-1 ring. Everything their edges reach that isn’t already found — D, E, F — forms the distance-2 ring. Then G and H at distance 3. BFS discovers the graph in exactly this banded order: it completely finishes one column before it touches the next.

Let’s build one, step by step

We’ll assemble the full class at the end. For now, one piece at a time, on that eight-node graph. The graph itself is an adjacency list — each node keyed to a list of its neighbours (if that representation is new, the graphs article builds it from scratch).

Step 1 — the queue and the visited mark

Two structures, straight from the office. A queue holds the nodes we’ve discovered but not yet spread from. A distance array does double duty: -1 means "not yet reached" (so it’s also our visited check), and any other value is the node’s ring number. We seed the source at distance 0 and drop it in the queue.

int[] dist = new int[n];
Arrays.fill(dist, -1);          // -1 = not yet reached (doubles as "unvisited")
Deque<Integer> queue = new ArrayDeque<>();
 
dist[source] = 0;               // the source is zero rings from itself
queue.add(source);              // it's the only one waiting to spread, for now

The rule: mark a node the instant it enters the queue, never when it leaves. We just did that — dist[source] is set the same moment source is enqueued. Why it matters is the subject of Step 3, and it’s the single most common way to break BFS.

Step 2 — the loop: pop the front, discover neighbours, enqueue

Now drain the queue. Take the node at the front (the one that’s been waiting longest), look at each neighbour, and for every neighbour we haven’t reached yet, stamp its distance as one more than the current node’s and add it to the back of the queue.

Follow those four snapshots. We seed [S]. We pop S and push its neighbours B, C. We pop B and push D, E. We pop C and push F (note E is already marked, so C doesn’t re-add it). The queue marches through the graph one ring at a time.

while (!queue.isEmpty()) {
    int node = queue.poll();            // take the front — FIFO
    for (int next : graph.get(node)) {
        if (dist[next] == -1) {         // first time we've reached `next`
            dist[next] = dist[node] + 1;
            queue.add(next);            // ...join the back of the line
        }
    }
}

The rule: front out, back in. A queue is first-in-first-out, so nodes leave in the exact order they arrived. That ordering is not a detail — it’s the entire reason the rings stay separated, which we’ll prove shortly.

Step 3 — the bug: marking too late

Here’s where nearly everyone slips, and interviewers know it. The mistake is to mark a node visited when you pop it instead of when you push it:

while (!queue.isEmpty()) {
    int node = queue.poll();
    if (seen[node]) continue;           // ← marking on the way OUT, too late
    seen[node] = true;
    for (int next : graph.get(node)) {
        if (!seen[next]) {
            queue.add(next);            // `next` isn't marked until it's popped!
        }
    }
}

Watch what goes wrong. S pushes B and C. Now suppose both B and C are neighbours of E. B gets popped, sees E unmarked, pushes it. Then C gets popped, also sees E unmarked (it won’t be marked until it’s finally popped), and pushes it again. The same node piles into the queue once for every edge pointing at it. On a dense graph the queue swells from O(V) toward O(E) entries, memory balloons, and work multiplies — your tidy linear scan quietly turns quadratic.

The fix is the rule from Step 1: mark the node the moment it’s enqueued, so a second edge that reaches it finds it already claimed and moves on. In our real code the dist[next] == -1 check is that mark — a node’s distance is stamped the instant it’s pushed, so it can never be pushed twice.

Step 4 — remembering the road, not just the distance

Distances tell you how far the stadium is. To recover the actual route, remember, for each node, who discovered it — its parent in the search. Then walk the parent pointers backward from the destination to the source and reverse them.

int[] parent = new int[n];
Arrays.fill(parent, -2);        // -2 = unseen; -1 = the source (no parent)
parent[src] = -1;
// ...inside the loop, when we first reach `next`:
//     parent[next] = node;
 
// afterwards, rebuild the route by walking parents back to the source:
LinkedList<Integer> path = new LinkedList<>();
for (int at = dst; at != -1; at = parent[at]) {
    path.addFirst(at);          // prepend, so the path comes out src → dst
}

Because a node’s parent is whoever first reached it, this reconstructed route is a genuine shortest path — the same guarantee we’re about to unpack, now doing real work.

Step 5 — peeling one ring at a time: the level-size trick

Sometimes you don’t want a flat distance per node — you want the nodes grouped by ring: everything at distance 1, then everything at distance 2. There’s a lovely trick for it. At the top of each pass, the queue holds exactly one full ring. Snapshot its size, then pop precisely that many nodes; every child you push belongs to the next ring, which quietly builds up behind them.

while (!queue.isEmpty()) {
    int size = queue.size();            // the whole current ring, snapshotted
    List<Integer> layer = new ArrayList<>();
    for (int i = 0; i < size; i++) {    // pop EXACTLY this ring, no more
        int node = queue.poll();
        layer.add(node);
        for (int next : graph.get(node)) {
            if (!seen[next]) {
                seen[next] = true;
                queue.add(next);        // children land in the next ring
            }
        }
    }
    layers.add(layer);                  // one entry per distance
}

The rule: grab queue.size() before the inner loop, and pop that many. Snapshot it too late — read the size while you’re still pushing children — and you’ll swallow the next ring into this one. This one trick powers "print a tree level by level," "the rightmost node on each level," and "the minimum number of steps," all with the same skeleton.

Why the first time you reach a node is the shortest way there

This is the claim the whole article rests on, and it deserves a real proof — not "trust me, it’s the queue." It’s the one genuinely deep idea in BFS, so let’s slow all the way down.

Look at that picture. Node T can be reached two ways: the short hop S → X → T (2 edges) and the scenic S → Y → Z → T (3 edges). BFS stamps T with distance 2 and never lets the longer route touch it. Why is it impossible for the 3-edge route to win the race?

The answer is a single invariant about the queue. Here it is:

At every moment, the distances of the nodes sitting in the queue are nondecreasing from front to back, and the largest and smallest differ by at most one.

In plain words: the queue only ever holds two adjacent rings — some leftovers of ring d near the front, then ring d+1 behind them. Never three rings, never out of order. You can see it in the queue snapshots from Step 2: the third snapshot holds C (distance 1) followed by D, E (distance 2), and nothing else.

Why does that invariant survive every step? Induction on the loop. It starts true: the queue is just [source], a single distance. Now assume it holds and we do one iteration — pop the front node u, at distance d (the smallest in the queue), and push u’s freshly-discovered neighbours at distance d+1 onto the back:

• Popping the front can only raise the smallest distance, from d to d or d+1. Still fine.
• Everything already in the queue was between d and d+1, so it was all ≤ d+1. We append nodes of distance d+1 to the back — the largest value going last — so the sequence stays nondecreasing and still spans at most one step. The invariant is preserved.

Now cash it out. Because the queue is always sorted by distance and we always pop the front, BFS dequeues nodes in nondecreasing order of distance — it fully finishes every node at distance d before it processes any node at distance d+1. So consider the first time any edge points at T, coming from some node u we’re currently processing. Could T secretly have a shorter path, of length k less than dist[u] + 1? A path of length k means T has a neighbour w at distance k − 1. But every node at distance k − 1 ≤ dist[u] was dequeued before u — and when w was processed, it would have discovered T right then. So T would already be marked before u ever looked at it. Contradiction. There is no shorter path; dist[u] + 1 is the true shortest distance.

There’s a deeper lesson tucked in here that pays off far beyond BFS. This whole argument only worked because every edge added the same amount — exactly one — to the distance. That’s what let a plain FIFO queue keep the rings sorted for free. The instant edges carry different weights, the closest-unfinished node is no longer the one that’s been waiting longest, and a FIFO queue can’t keep the order. You need a structure that always coughs up the smallest-distance node regardless of arrival time — a priority queue — and swapping the queue for one is precisely the leap from BFS to Dijkstra’s algorithm. BFS is Dijkstra’s lucky special case, where all weights are 1 and the ordinary queue happens to already be a priority queue.

BFS on a grid

A grid — a maze, a game board, an image — is secretly a graph. Each cell is a node, and its "neighbours" are the cells you can step to: the 4 orthogonal ones (up, down, left, right), or 8 if diagonals count too. You rarely build an adjacency list; you just compute neighbours on the fly with a little list of coordinate offsets.

The left side is the stencil — from cell c, the four moves are (±1, 0) and (0, ±1). The right side floods from one source, and because every step costs one, the distances grow in tidy Manhattan-distance rings, exactly like ripples in the pond. Everything else is ordinary BFS, with a two-number coordinate standing in for a node id and a bounds check standing in for "is this a real neighbour."

private static final int[][] DIRS4 = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
 
public static int gridShortestPath(int[][] grid, int sr, int sc, int tr, int tc) {
    int rows = grid.length, cols = grid[0].length;
    boolean[][] seen = new boolean[rows][cols];
    Deque<int[]> queue = new ArrayDeque<>();
    seen[sr][sc] = true;
    queue.add(new int[] {sr, sc, 0});           // row, col, distance-so-far
    while (!queue.isEmpty()) {
        int[] cur = queue.poll();
        int r = cur[0], c = cur[1], d = cur[2];
        if (r == tr && c == tc) return d;        // reached the goal
        for (int[] dir : DIRS4) {
            int nr = r + dir[0], nc = c + dir[1];
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                    && !seen[nr][nc] && grid[nr][nc] == 0) {   // in bounds, open, unseen
                seen[nr][nc] = true;             // mark on enqueue, as always
                queue.add(new int[] {nr, nc, d + 1});
            }
        }
    }
    return -1;                                   // target walled off
}

The payoff is that BFS routes around walls for free. Drop a wall between start and goal and the flood simply bends around it, and the distance it reports is the true shortest way through the maze — no special "wall-following" logic anywhere.

Multi-source BFS

Here’s a twist that looks like it should need a rewrite and needs almost none. Instead of "how far is every cell from this source?", ask "how far is every cell from the nearest of several sources?" — the nearest fire exit, the nearest already-rotten orange, the closest gate.

The naive plan is to run a separate BFS from each source and take the minimum, which costs you one full sweep per source. The trick: seed every source into the same queue at distance 0, then run a single ordinary BFS. Their rings expand simultaneously and collide in the middle; because BFS still hands nodes out in nondecreasing distance, whichever source reaches a cell first is, by definition, its nearest.

Deque<int[]> queue = new ArrayDeque<>();
for (int[] s : sources) {           // EVERY source starts at distance 0
    if (dist[s[0]][s[1]] == -1) {
        dist[s[0]][s[1]] = 0;
        queue.add(new int[] {s[0], s[1]});
    }
}
// ...then the identical BFS loop from here on.

That’s the entire change: many seeds, one queue, one pass. The O(V + E) cost doesn’t budge no matter how many sources you throw in — a genuinely elegant win, and a favourite interview escalation.

BFS vs the obvious alternatives

BFS shares its O(V + E) skeleton with depth-first search, but they answer different questions, and neither is Dijkstra. Let V be the vertices and E the edges.

The split with DFS is the one to internalise: same cost, opposite instinct. DFS follows one branch to the bitter end before backtracking — perfect for "can I reach it at all?" or "is there a cycle?", useless for "what’s the closest one," because the first route it stumbles onto is rarely the shortest. BFS trades the stack for a queue and gets shortest-by-hops as a guarantee. Dijkstra is the paid upgrade for when hops become costs.

Why is BFS O(V + E) and not worse? Because "mark on enqueue" means each vertex is enqueued and dequeued exactly once, and each time we dequeue a vertex we scan its edges exactly once:

That sum of degrees equals 2E on an undirected graph (every edge has two ends), so the total work is proportional to the size of the graph itself — you can’t do asymptotically better, since you have to look at each node and edge at least once.

The complete implementation

Everything above, assembled — plain distances, path reconstruction, level grouping, the grid variant, and multi-source, in one class:

package dev.fiveyear.bfs;
 
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
 
public final class BreadthFirstSearch {
 
    private BreadthFirstSearch() {}
 
    private static final int[][] DIRS4 = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
 
    /** Shortest distance (in edges) from source to every node; -1 if unreachable. O(V + E). */
    public static int[] distances(List<List<Integer>> graph, int source) {
        int n = graph.size();
        int[] dist = new int[n];
        Arrays.fill(dist, -1);
        Deque<Integer> queue = new ArrayDeque<>();
        dist[source] = 0;
        queue.add(source);
        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int next : graph.get(node)) {
                if (dist[next] == -1) {          // first reach: stamp and enqueue
                    dist[next] = dist[node] + 1;
                    queue.add(next);
                }
            }
        }
        return dist;
    }
 
    /** A shortest path from src to dst as a node list, or empty if unreachable. O(V + E). */
    public static List<Integer> shortestPath(List<List<Integer>> graph, int src, int dst) {
        int n = graph.size();
        int[] parent = new int[n];
        Arrays.fill(parent, -2);                 // -2 = unseen, -1 = source (no parent)
        Deque<Integer> queue = new ArrayDeque<>();
        parent[src] = -1;
        queue.add(src);
        while (!queue.isEmpty()) {
            int node = queue.poll();
            if (node == dst) break;              // found it — earliest reach is shortest
            for (int next : graph.get(node)) {
                if (parent[next] == -2) {
                    parent[next] = node;
                    queue.add(next);
                }
            }
        }
        if (parent[dst] == -2) return List.of(); // never reached
        LinkedList<Integer> path = new LinkedList<>();
        for (int at = dst; at != -1; at = parent[at]) {
            path.addFirst(at);                   // walk parents back, prepend to reverse
        }
        return path;
    }
 
    /** Nodes grouped by distance: layer 0 = {source}, layer 1 = its neighbours, and so on. */
    public static List<List<Integer>> levels(List<List<Integer>> graph, int source) {
        int n = graph.size();
        boolean[] seen = new boolean[n];
        List<List<Integer>> layers = new ArrayList<>();
        Deque<Integer> queue = new ArrayDeque<>();
        seen[source] = true;
        queue.add(source);
        while (!queue.isEmpty()) {
            int size = queue.size();             // one full ring, snapshotted
            List<Integer> layer = new ArrayList<>();
            for (int i = 0; i < size; i++) {     // pop exactly this ring
                int node = queue.poll();
                layer.add(node);
                for (int next : graph.get(node)) {
                    if (!seen[next]) {
                        seen[next] = true;
                        queue.add(next);
                    }
                }
            }
            layers.add(layer);
        }
        return layers;
    }
 
    /** Fewest steps from (sr,sc) to (tr,tc) on a grid of 0 = open, 1 = wall; -1 if blocked. */
    public static int gridShortestPath(int[][] grid, int sr, int sc, int tr, int tc) {
        int rows = grid.length, cols = grid[0].length;
        if (grid[sr][sc] == 1 || grid[tr][tc] == 1) return -1;
        boolean[][] seen = new boolean[rows][cols];
        Deque<int[]> queue = new ArrayDeque<>();
        seen[sr][sc] = true;
        queue.add(new int[] {sr, sc, 0});
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int r = cur[0], c = cur[1], d = cur[2];
            if (r == tr && c == tc) return d;
            for (int[] dir : DIRS4) {
                int nr = r + dir[0], nc = c + dir[1];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                        && !seen[nr][nc] && grid[nr][nc] == 0) {
                    seen[nr][nc] = true;
                    queue.add(new int[] {nr, nc, d + 1});
                }
            }
        }
        return -1;
    }
 
    /** Distance from every open cell to its NEAREST source, in a single pass. -1 = unreachable. */
    public static int[][] nearestSourceDistance(int[][] grid, int[][] sources) {
        int rows = grid.length, cols = grid[0].length;
        int[][] dist = new int[rows][cols];
        for (int[] row : dist) Arrays.fill(row, -1);
        Deque<int[]> queue = new ArrayDeque<>();
        for (int[] s : sources) {                // seed every source at distance 0
            if (grid[s[0]][s[1]] == 0 && dist[s[0]][s[1]] == -1) {
                dist[s[0]][s[1]] = 0;
                queue.add(new int[] {s[0], s[1]});
            }
        }
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int r = cur[0], c = cur[1];
            for (int[] d : DIRS4) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                        && dist[nr][nc] == -1 && grid[nr][nc] == 0) {
                    dist[nr][nc] = dist[r][c] + 1;
                    queue.add(new int[] {nr, nc});
                }
            }
        }
        return dist;
    }
}

And here it is producing exactly the outputs the comments claim, on the eight-node graph we drew (S = 0, B = 1, C = 2, D = 3, E = 4, F = 5, G = 6, H = 7):

// adjacency list for the overview graph, built undirected
List<List<Integer>> g = new ArrayList<>();
for (int i = 0; i < 8; i++) g.add(new ArrayList<>());
int[][] edges = {{0,1},{0,2},{1,3},{1,4},{2,4},{2,5},{3,6},{4,6},{5,7}};
for (int[] e : edges) { g.get(e[0]).add(e[1]); g.get(e[1]).add(e[0]); }
 
BreadthFirstSearch.distances(g, 0);      // [0, 1, 1, 2, 2, 2, 3, 3]
BreadthFirstSearch.shortestPath(g, 0, 6);// [0, 1, 3, 6]  — a 3-edge shortest route to G
BreadthFirstSearch.levels(g, 0);         // [[0], [1, 2], [3, 4, 5], [6, 7]]
 
int[][] maze = {
    {0, 0, 0},
    {1, 1, 0},   // a wall between the top row and the bottom
    {0, 0, 0},
};
BreadthFirstSearch.gridShortestPath(maze, 0, 0, 2, 0);  // 6 — forced the long way around
 
int[][] open = new int[3][5];            // no walls; sources at opposite corners
int[][] two = {{0, 0}, {2, 4}};
BreadthFirstSearch.nearestSourceDistance(open, two);
// row 0: [0, 1, 2, 3, 2]
// row 1: [1, 2, 3, 2, 1]
// row 2: [2, 3, 2, 1, 0]   ← each cell's distance to whichever corner is closer

Notice the maze case: a straight drop from (0,0) to (2,0) is two steps, but the wall forces the flood out to the right and back, and BFS faithfully reports 6 — the true shortest way through. And the multi-source grid needs only one pass to label every cell with its distance to the nearer corner.

The interview corner

BFS is one of the most-asked graph patterns precisely because the naive shape is easy and the guarantee behind it is subtle. Walk in knowing the questions to ask and the ladder they’ll climb.

Ask these before you write a line:

• "Is the graph unweighted — does every edge count as one step?" This is the whole ballgame. Unweighted → BFS gives shortest paths. Weighted → BFS is wrong and you want Dijkstra (or 0-1 BFS for weights of only 0 and 1). Establishing it first shows you know why BFS works.
• "Am I searching a graph I’m given, or an implicit one — a grid, a set of states?" Grids and puzzles rarely hand you an adjacency list; you generate neighbours on the fly. Say which, because it changes the code shape.
• "One source, or many? Do I need the distance, the actual path, or just yes/no reachability?" Many sources → multi-source seed. A path → keep parent pointers. Reachability → a plain visited flood. Each is a one-line difference, and naming it up front is the signal.

The follow-up ladder — where a strong candidate keeps climbing:

1. "Return the path, not just the length." Keep a parent[] set the moment each node is discovered, then walk it back from the destination and reverse. First-reach is shortest, so the reconstructed route is a genuine shortest path.
2. "The grid has diagonal moves too." Swap the 4-offset stencil for an 8-offset one — (±1, 0), (0, ±1), (±1, ±1). The whole engine is unchanged; only the neighbour list grows.
3. "Edges are weighted 0 or 1." A plain queue can’t keep the rings sorted once weights differ — but for only 0 and 1, use a deque: push 0-weight neighbours to the front, 1-weight to the back. That "0-1 BFS" keeps distances ordered in O(V + E), no heap.
4. "Search from both ends." For a single source and single target on a huge graph, run BFS from both and stop when the frontiers meet. Bidirectional BFS explores roughly 2·b^(d/2) nodes instead of b^d — a massive cut on deep graphs, at the cost of trickier bookkeeping.
5. "Now the edges have real, varied weights." BFS can’t; the closest node is no longer the longest-waiting one. Reach for a priority queue and you have Dijkstra; add a heuristic that estimates remaining distance and you have A*.

Three mistakes that fail the round:

• Marking visited on dequeue instead of enqueue. The same node piles into the queue once per incoming edge, and a linear algorithm goes quadratic in memory and time. Mark the instant you push.
• Using BFS on a weighted graph. The ring logic silently returns a fewest-edges path, not a shortest-cost one — a wrong answer that looks right on unweighted test cases. Check the weights before you reach for the queue.
• Reading queue.size() inside the level loop. In the level-by-level variant, the size must be snapshotted before you start popping — read it late and the children you push get swept into the current ring, corrupting every distance after the first.

Where to go from here

You now own the core: a queue of the discovered-but-not-yet-spread, a visited mark stamped on enqueue, and rings that fan out one step at a time — so the first time you touch a node, you’ve found the shortest way there. Three natural next stops:

• Depth-first search — the same O(V + E) skeleton with a stack instead of a queue, diving deep instead of spreading wide. It’s the tool for cycle detection, topological sort, and connected components; start from the graphs article.
• Dijkstra and A* — BFS with a priority queue, for when edges carry real costs. This is the single most common interview escalation from BFS; the mechanism is in Dijkstra’s algorithm.
• 0-1 BFS and bidirectional BFS — the two refinements that keep BFS’s linear speed while stretching what it can do, one into lightly-weighted graphs, the other into enormous ones.

Next time your network app prints a quiet "2nd" beside a stranger’s name, you’ll know exactly what happened: a ripple spread out from you across a billion people, a queue drained one ring at a time, and the very first ring to reach them was — guaranteed — the shortest one.