In BFS, how do you track which layer you are on, and how does that differ from recovering a route?
answer
- hop count and route are different outputs
- what does the frontier hold at pass start
- read the size before draining
- one stored link per discovered node
- walk backwards from the target, then reverse
basics
~20 sSnapshot the queue size at the top of each pass and drain exactly that many nodes: that block is one layer, which answers how many hops. Recovering the route needs a stored discoverer per node, walked backwards from the target.
solid answer
~50 sTwo different questions need two different pieces of bookkeeping. For "how many hops", either read the frontier's size at the top of the loop and drain exactly that many nodes — that block is one complete layer, so a counter incremented per pass is the current depth — or store a distance per node, assigned as `dist[v] = dist[u] + 1` at the moment `v` is discovered. The snapshot form costs nothing per node and gives you a global depth; the distance array costs O(V) and answers for every node independently. For "which route", neither is enough: you record, per node, the node that discovered it. Those parent links form the BFS tree, and walking them back from the target and reversing gives one minimum-hop route in time proportional to its length. What you must not do is carry whole candidate routes in the frontier — that multiplies memory by the path length for no gain.
code
pseudocode · 13 linesenqueue(Q, s)
visited[s] = true
depth = 0
while Q is not empty:
width = size(Q)
for i in 1..width:
u = dequeue(Q)
// u is exactly depth hops from s
for v in neighbors(u):
if visited[v] == false:
visited[v] = true
enqueue(Q, v)
depth = depth + 1go deeper
Recall that BFS by itself only orders the visits. Know that a hop count needs a counter or a per-node distance, and that returning the actual route needs you to remember, for each node, which node discovered it.
Explain the layer-snapshot invariant — at the top of each pass the frontier holds exactly the current level — and why the size must be read before draining. Contrast the cost of a depth counter, a distance array and a parent array.
Show judgment about what to store. Recognise the memory trap of carrying routes inside frontier entries, and pick the minimum bookkeeping the requested output actually needs rather than instrumenting everything by reflex.
Own the interface question: what the traversal promises callers. Committing to return routes rather than distances fixes an O(V) memory cost and a tie-breaking policy into the contract, and promising all minimum-hop routes commits to an output that can be exponentially large.
## Three separate pieces of bookkeeping A plain BFS visits nodes in the right order and tells you nothing else. Everything you might want out of it — the current depth, each node's distance, the actual route — is a *deliberate* extra you attach, and each has a different cost. ### 1. Layer-size snapshot — "how deep am I now?" At the top of each outer pass, read the frontier's current size into a local. That number is exactly the number of nodes at the current depth, because everything appended during this pass belongs to the next depth. Drain precisely that many, then increment a depth counter. The invariant is clean: **on entry to pass number `d`, the frontier contains exactly the nodes at distance `d`, and nothing else.** Cost: one integer. No per-node storage. What you get is a global notion of "we are now `d` hops out", which is what you want when the question is "how many hops until some condition holds?" — you stop the moment the condition fires and report `d`. ### 2. Distance per node — "how far is each one?" Assign `dist[v] = dist[u] + 1` at discovery time, in the same place you set the visited flag. This costs O(V) storage and answers per node rather than globally, which is what you need when the result is a whole distance field rather than a single number. It also subsumes the visited marking: an unassigned distance *is* an unvisited node, so many implementations keep one structure instead of two. A subtlety worth stating: assign at **discovery**, not at removal. Assigning at removal reintroduces the window in which a node can be discovered twice, and any later assignment risks overwriting the good value. ### 3. Parent links — "which route?" When `v` is discovered from `u`, record `parent[v] = u`. Those links form the **BFS tree**: a spanning tree of the reachable region rooted at the source, in which the tree path from the root to any node is a minimum-hop route to it. To produce the route to a target, start at the target, follow parent links to the source, and reverse. That costs O(path length) time and no extra memory beyond the parent array itself. The wrong instinct here is to store, in each frontier entry, the whole route that reached it. It works, and it is a genuine memory trap: instead of one identifier per node you carry up to a path's worth per frontier entry, multiplying peak memory by the depth for information you can reconstruct in linear time from single links. ## Depth is derivable from parents, but not cheaply Parent links contain the distance information — walk to the root and count — but that walk is O(depth) per query. If you need distances for many nodes, store distances. If you need routes, store parents. If you need both, store both; together they are two O(V) arrays, which is the same order as the visited marking you already pay for. ## What the BFS tree tells you about the graph The tree is not just a route-recovery device; its shape is a fact about the graph. In an **undirected** graph, every edge connects two nodes whose BFS levels differ by **at most one** — there are tree edges between consecutive levels and non-tree edges either between consecutive levels or within a single level, and never an edge that skips a level. The reason is immediate from the traversal: if an edge joined level `d` to level `d+2`, then when the level-`d` endpoint was expanded, the other endpoint would have been discovered at `d+1`, contradiction. That single sentence is the basis for several results built on BFS layering, and it is a good thing to be able to derive rather than recite. On a **directed** graph the statement weakens: a directed edge may jump backwards across many levels, because the traversal only ever followed out-edges. ## Ties A node can be reachable at its minimum distance through several different predecessors. BFS records whichever discovered it first, which is decided by neighbour ordering — so the route you get back is one valid minimum-hop route, not a canonical one. If you must enumerate all of them, record *every* predecessor at the minimum distance instead of one, and the structure stops being a tree and becomes a layered graph. Be careful before promising that: the number of distinct minimum-hop routes can be exponential in the depth, even though storing all the predecessor links is only O(E). ## Choosing in the room When an interviewer describes the output they want, name the bookkeeping before writing anything: a single hop count means a size snapshot; a distance field means an array assigned at discovery; a route means parent links walked backwards. Getting that mapping right in the first sentence is most of the answer.
- You need the distance to every node, not just the current depth. What changes?Replace the global counter with a per-node distance assigned at discovery: `dist[v] = dist[u] + 1`, set in the same place as the visited flag. That is O(V) extra storage and answers independently for each node. It also subsumes the visited marking, since an unassigned distance is precisely an undiscovered node.
- Once the target is reached, how do you turn parent links into the route, and what does it cost?Start at the target, follow parent links until you reach the source, then reverse the sequence. Time and extra memory are proportional to the route's length, not to the graph, because the links are already stored. The alternative — carrying whole candidate routes inside frontier entries — multiplies peak memory by the depth for no benefit.
- Can a node legitimately have more than one valid parent?Yes, whenever it is reachable at its minimum distance through several predecessors. BFS keeps whichever discovered it first, decided by neighbour ordering, so the route you recover is one valid answer rather than a canonical one. Enumerating all of them means storing every minimum-distance predecessor — O(E) links, but potentially exponentially many distinct routes.
saying these in an interview costs you the question
- Stores whole candidate routes in each frontier entry
- Reads the frontier size after draining instead of before
- Thinks a hop count alone can reconstruct the route
- Assigns the distance at removal instead of at discovery
- Claims BFS returns the one canonical minimum-hop route
- Believes an undirected edge can skip a BFS level