A mesh dashboard asks “how many hops from this gateway to payments?” The code recurses into the first neighbor, then that neighbor’s first neighbor, and reports an 11-hop chain through sidecars. There is a 2-hop route. Nobody “chose a slow graph algorithm.” They walked depth-first and treated the first path they found as the shortest.

BFS visits vertices in order of increasing hop count because the frontier is a FIFO queue. First time you see a vertex is the unweighted shortest path to it. Same loop is level order: everyone at distance d, then d + 1.

This post is that procedure. Families and Big-O literacy live on the Algorithms Roadmap. The layout — adjacency list vs matrix, directed vs not — lives on Graphs. Walks consume that layout; they do not choose it. The frontier type is a Queue: ArrayDeque, not a stack, not ArrayList.remove(0).

This is not Dijkstra, not a maze toy, and not tree-traversal-as-layout. Binary trees already own level-order on a tree. Here the graph can have cycles, cross edges, and more than two children.

The frontier is a queue

Start at s. The queue holds vertices you have discovered but not yet expanded. Dequeue the oldest. For each unseen neighbor, record “I got here from u” and enqueue it. Repeat until the queue is empty (or you dequeued the goal).

FIFO is the algorithm. The vertex that has been waiting longest is the one with the smallest hop count still on the frontier. Its unseen neighbors are therefore one hop farther — never closer. You will not discover a shorter unweighted path later, because every shorter candidate would have been dequeued already.

Mark a vertex when you enqueue it, not when you dequeue it. If you wait until dequeue, the same vertex can sit in the queue many times, once per incoming edge. Set.add returning false is the whole filter.

Note: “Seen” is not cycle detection. That post owns colors and back edges. Here seen only means “do not put this vertex on the frontier twice.” A cycle without seen is an infinite enqueue.

Why the frontier must not be a stack

Replace the queue with a stack (or with recursion, which is a stack) and the oldest vertex is no longer next. You expand the neighbor you just discovered — deeper, not broader. First time you reach payments might be gateway → auth → catalog → payments (three hops) even though gateway → payments exists.

That walk is DFS. It is a legal visit order. It is not hop order. A stack frontier is DFS wearing a BFS name. The first path it prints is “a path,” not “a shortest path.”

LIFO also breaks the invariant that everything already dequeued is closer than everything still on the frontier. Once that dies, “first visit = shortest” dies with it. Weighted shortest path has a different cousin — Dijkstra — and a different frontier (a heap of best-known distances). This post does not run that argument. If every edge is one hop, you do not need a heap.

Level order is the same loop

Hop count is the level. Process the start (distance 0), then every vertex at distance 1, then 2, and so on. You do not need a second algorithm for “print by rank.” Snapshot the queue size at the start of a round; that many dequeues are the current level.

On a tree, level-order in the binary-tree post is this procedure with no seen set, because you never follow a parent pointer back. On a graph you need seen: an undirected edge is a two-way door, and a directed graph can still point at a vertex already on the frontier. Parent pointers from one start are a BFS tree; vertices you never enqueue are in another component.

Unweighted shortest path

Each edge costs one. The length of a path is the number of edges. BFS’s first visit to t is a minimum-length path from s to t, and the parent map reconstructs it.

If edges have lengths (latency, kilometers, fees), hop count is the wrong objective. A 3-hop route can beat a 1-hop expensive edge. That job is Dijkstra when weights are non-negative — named here so you do not paste a PriorityQueue into an unweighted service graph and call it done.

directed hops (service calls):

  gw → auth
  gw → pay
  auth → pay
  auth → catalog
  pay → catalog
  pay → ledger

start gw, goal catalog

queue / seen / parent  (mark on enqueue)

  enqueue gw          seen {gw}              parent gw=—
  dequeue gw
    enqueue auth      dist 1  parent auth=gw
    enqueue pay       dist 1  parent pay=gw
  queue: auth, pay

  dequeue auth
    pay already seen — skip
    enqueue catalog   dist 2  parent catalog=auth
  queue: pay, catalog

  dequeue pay
    catalog already seen — skip
    enqueue ledger    dist 2  parent ledger=pay
  queue: catalog, ledger

  dequeue catalog     first visit, dist 2
  path: gw → auth → catalog

DFS from gw that recurses auth first can report
  gw → auth → pay → catalog   (3 hops)
and never notice the 2-hop routes.

gw → pay → catalog is also two hops. First discovery wins; BFS does not promise a particular two-hop path, only that no shorter one exists. ledger is discovered at distance 2 as well, from pay. Vertices never enqueued are unreachable from gw.

Java sketch

The graph is a map of neighbor lists — the sparse default from the Graphs post. The frontier is ArrayDeque as a Queue. seen.add(v) is the enqueue gate.

static Map<String, String> bfsParent(
        Map<String, List<String>> g, String start) {
    Map<String, String> parent = new HashMap<>();
    Set<String> seen = new HashSet<>();
    Queue<String> frontier = new ArrayDeque<>();
    seen.add(start);
    frontier.add(start);

    while (!frontier.isEmpty()) {
        String u = frontier.remove();
        for (String v : g.getOrDefault(u, List.of())) {
            if (seen.add(v)) {
                parent.put(v, u);
                frontier.add(v);
            }
        }
    }
    return parent;
}

parent has no entry for start. Walk toward it and reverse:

static List<String> path(Map<String, String> parent, String start, String goal) {
    if (goal.equals(start)) {
        return List.of(start);
    }
    if (!parent.containsKey(goal)) {
        return List.of(); // unreachable
    }
    List<String> out = new ArrayList<>();
    for (String v = goal; v != null; v = parent.get(v)) {
        out.add(v);
        if (v.equals(start)) {
            Collections.reverse(out);
            return out;
        }
    }
    return List.of();
}

Level order is a width snapshot on the same queue, not a different search:

int dist = 0;
while (!frontier.isEmpty()) {
    int width = frontier.size();
    for (int i = 0; i < width; i++) {
        String u = frontier.remove();
        // u is at hop count dist
        for (String v : g.getOrDefault(u, List.of())) {
            if (seen.add(v)) {
                frontier.add(v);
            }
        }
    }
    dist++;
}

Do not use LinkedList as the default FIFO — the Queue post already priced that node object. Do not recurse and claim hop-shortest. Stop early when you dequeue the goal if you only need one target; first-visit distances for anyone already enqueued stay valid.

Complexity

Let V be vertices, E edges. Each vertex is enqueued at most once. Each edge is examined when its tail is expanded.

TimeO(V + E) on an adjacency list (each vertex and edge a constant number of times)
Extra RAMThe queue + seen + parent — O(V), worst-case the whole component
DistanceHop count; first visit is minimum hops

A matrix still runs the same loop; neighbor iteration then scans |V| cells per vertex — pick the layout on the Graphs post. The bill that kills the mesh dashboard is the wrong visit order, not a missing log V.

When not to BFS

Skip this procedure when:

  • Edges have lengths. Hop-shortest is not cost-shortest. Dijkstra (non-negative weights) is the weighted cousin. Do not put a PriorityQueue on a graph where every edge is already 1.
  • You needed finish times, a recursion stack, or “is there a back edge.” That is DFS (and cycle detection). BFS will visit everyone; it will not hand you a finish timestamp.
  • The shape is a tree and you only wanted level-order print. Use the tree walk you already have. Adding seen on a tree is harmless and usually noise.
  • You needed any path, or only connectivity, and the graph is huge. BFS still works; DFS (or an explicit stack) is the other complete walk. Neither is “faster Big-O” on an adjacency list. Pick the order the job asked for.

Do not report the first DFS path as shortest hops. Do not run a heap search because “shortest path” sounded weighted. Skip a custom walk when a graph store or control plane already answers hop count.

JDK: a queue, not a Bfs class

There is no java.util.Bfs. The library pieces are:

  • Frontier: Queue + ArrayDeque
  • Seen: HashSet
  • Parent / distance: HashMap, or parallel arrays if vertices are 0 … n-1
  • Layout: Map<K, List<K>> (or a matrix if you already chose one)

Prefer ArrayDeque as the frontier in single-threaded code. Reach for PriorityQueue only when the next vertex is best known distance, not oldest discovered. That heap is Dijkstra’s layout, not this post’s. Do not implement a queue. Do not use Stack.

Cheat sheet

Job:        hop order from a start; unweighted shortest path; level order
Frontier:   FIFO queue (ArrayDeque) — oldest = smallest hop count still live
Invariant:  first visit is minimum hops; mark seen on enqueue
Level:      snapshot queue size; that many vertices share a distance
Path:       parent pointers; walk goal → start and reverse
Time / RAM: O(V + E) list / O(V) extra
Cousin:     Dijkstra when edges have non-negative weights
Tree case:  level-order without seen (binary-tree post)
Do not:     stack/recursion as "BFS"; heap on unweighted hops

Do:

  • Enqueue the start, mark it seen, expand neighbors that seen.add accepts.
  • Snapshot frontier.size() when you need explicit levels.
  • Reconstruct with a parent map; empty list means unreachable.

Don’t:

  • Use a stack (or recursion) and call the first path shortest.
  • Mark seen only on dequeue and let the queue fill with duplicates.
  • Run Dijkstra because the ticket said “shortest path” and every edge is one hop.
  • Count roads on a weighted map and call the hop total a shortest path.

Wrap-up

BFS is hop order. The frontier is a queue so the next vertex you expand is the closest one you have not expanded yet. Level order is that loop with a width snapshot. Unweighted shortest path is that loop plus parent pointers. A stack is DFS: a legal walk, the wrong distance. Weighted edges need a different cousin. The JDK gives you ArrayDeque and a set, not a Bfs class. Hand-roll the walk when the graph is yours and hop count is the question. Otherwise ask the store that already knows the edges.

The next walk in this wave is the stack-shaped one: finish times, recursion vs an explicit stack, and what a cycle looks like.

Next optional step in the series Finish times, recursion vs an explicit stack, and what a cycle looks like. DFS: Finish Times, Recursion vs an Explicit Stack