Breadth-first search — every question, written out
Explores a graph in rings of increasing distance. The queue is the whole idea: first discovered, first explored. First paths found are shortest paths.
Read the breadth-first search explanation and watch it run
Why is BFS O(V + E)? Derive it from what the loop actually does.
Complexity derivation
Each node is queued and dequeued once, and each node’s edges are inspected once when it is dequeued
The visited check admits each node to the queue at most once, so enqueue and dequeue together contribute O(V). Every dequeue then walks that node’s adjacency list exactly once, and summing adjacency-list lengths over all nodes gives 2E on an undirected graph. Adding the two independent costs, not multiplying them, is the whole derivation.
See it run — A leaves the frontier the moment its own three edges have been inspected — it is never revisited.
On Prism’s 12-node cycle graph the trace records 11 tree edges and 15 rejected edges. Where does 15 come from?
Complexity derivation
The 13 undirected edges are inspected from both ends — 26 inspections, of which 11 discover a node
An undirected edge appears in both endpoints’ adjacency lists, so BFS looks at it twice: 13 edges give 26 inspections. Exactly V − 1 = 11 of those are the first arrival at a node and become tree edges; the other 15 find a distance label already there and are rejected. This is the O(E) term made countable, and the counters panel lets you check it rather than trust it.
See it run — The edge B → A is rejected — it is the same edge A → B that was a tree edge four steps earlier.
BFS is O(V) space. Which part of that bound actually bites in practice?
Complexity derivation
The queue’s peak size, which is the widest level and can be a large fraction of V
Every term here is O(V), so the asymptotics do not distinguish them — the constant and the shape do. On a bushy graph a single level can hold most of the graph at once, which is why BFS over a branching state space runs out of memory long before it runs out of time. That is the pressure bidirectional search is designed to relieve.
Given that, why does searching from both ends at once help — and what does it cost you?
Trade-off & selection
Two frontiers of depth d/2 are far smaller than one of depth d, but you need the reverse graph and a meeting test
With branching factor b, one frontier at depth d holds about b^d nodes while two frontiers at depth d/2 hold about 2·b^(d/2) — a difference of many orders of magnitude on the graphs where BFS hurts. The price is real: you must be able to walk edges backwards, you must alternate the two searches to keep the frontiers balanced, and the shortest path is only confirmed after checking the level where they first touch. It is a single-pair technique, so it buys nothing for the single-source-to-all problem.
What does the FIFO queue guarantee that a stack would destroy?
Invariant identification
That nodes are explored in non-decreasing order of distance, so the first label assigned is the smallest
First discovered, first explored means a node at distance d is dequeued before any node at distance d + 1, so its neighbours are labelled d + 1 by the earliest possible discoverer. Replace the queue with a stack and the container still works, the search still terminates, and every node still gets a label — but the labels are path lengths down whatever branch happened to be taken, which is depth-first search. The queue is not an implementation detail; it is the shortest-path proof.
Now suppose the edges carry weights. Can BFS be patched to handle them?
Trade-off & selection
No — BFS orders by hop count, and a cheap two-hop route can be labelled after an expensive one-hop route
BFS commits a label the first time it touches a node, and that commitment is safe only because every edge costs the same. With weights, a path of two edges costing 1 each beats a single edge costing 10, yet BFS reaches the far end via the single edge first and never reconsiders. Restoring correctness means ordering the frontier by accumulated cost rather than by arrival — a priority queue — and that algorithm is Dijkstra.
And if every weight is either 0 or 1 — do you still need the heap?
Trade-off & selection
No — a deque suffices: push zero-weight neighbours to the front and weight-one neighbours to the back
The deque holds at most two distinct distance values at any moment, so front-loading the free edges keeps it sorted without a comparison-based structure. That gives O(V + E) instead of O((V + E) log V), which matters on grid problems where "turning costs 1, going straight is free" is the whole model. It is the standard escalation after weighted BFS, and naming it is worth more than deriving Dijkstra again.
The queue holds nodes labelled 1, 1, 2, 2, 2, 2. Could it ever hold a 1 and a 3 at the same time?
Invariant identification
No — a distance-3 node is only enqueued by a distance-2 node, and those are dequeued after every 1
A node labelled 3 can only be enqueued while a node labelled 2 is being explored, and every node labelled 1 was enqueued before every node labelled 2, so FIFO order guarantees the 1s have already left. The queue therefore spans at most two consecutive levels. That single clause is the mechanical form of "all nodes closer than the queue front are finished", which is what makes a later edge unable to improve a label.
See it run — The queue reads [D, J, C, F, K, L] — two nodes at distance 1 and four at distance 2, never a 3.
A candidate moves the visited check from enqueue time to dequeue time. What actually goes wrong?
Code diagnosis
A node still in the queue can be discovered again and enqueued twice, so the queue bloats past O(V)
Prism sets the distance and pushes in the same breath, which is what caps queue entries at one per node. Deferring the mark lets every incoming edge push a fresh copy, so a node of degree d can appear d times and the queue grows with E rather than V. The output is still correct, which is precisely what makes this bug survive code review and then fall over on a dense graph.
See it run — B is given distance 1 and enters the queue in consecutive steps — discovery and marking are one moment.
The queue holds [B, D, J] and all three are at distance 1. Which is explored next, and why?
Trace prediction
B — it entered the queue first, and FIFO order serves the longest-waiting node
Prism dequeues from the front, so B goes first because A discovered it before D and J. Within one level the choice does not change any distance label, but it does change which edges become tree edges and therefore which shortest path is reported when several are tied. That is why "the BFS tree" is really "a BFS tree".
See it run — The prediction prompt names the queue contents just before the dequeue that answers it.
The trace rejects the edge B → A, saying A was already discovered. What does that rejection prove?
Trace prediction
That a route to A no longer than this one already exists, so this edge cannot improve anything
Rejections are not wasted work — each one is a small proof that BFS already found a route to that node at most as short as the one on offer. In an undirected graph, V − 1 inspections discover a node and every remaining inspection is a rejection of exactly this kind. Reading them as evidence rather than noise is what makes the counters panel worth watching.
See it run — The rejection reason names A’s existing distance — that label is the proof the edge is too late.
On Prism’s islands preset BFS stops with six of twelve nodes labelled. Is that a bug in the search?
Edge case reasoning
No — BFS explores one component; reaching every node needs an outer loop over unvisited starts
A single BFS answers "what is reachable from this start", and on a disconnected graph that is strictly less than the whole graph. Counting islands or labelling every node needs the outer loop: for each node, if unvisited, launch a fresh search. Forgetting that loop is the standard failure on "count the connected components" problems, and it passes every connected test case.
See it run — The run ends with A–F labelled and the second island untouched — no edge ever crossed.
What does BFS do on a complete graph of V nodes, and what is the peak queue size?
Edge case reasoning
The first dequeue labels every other node at distance 1, so the queue peaks at V − 1
Expanding the start pushes all V − 1 neighbours at once, which is the worst case for BFS memory: the frontier is the entire graph minus one node. Every subsequent dequeue then inspects V − 1 edges and rejects all of them, giving the O(E) = O(V²) time term. It is the cleanest illustration of why BFS space is a queue problem rather than a visited-set problem.
You need each cell’s distance to the *nearest* of several sources. What changes in the BFS?
Edge case reasoning
Seed the queue with every source at distance 0; the rest of the algorithm is untouched
The level invariant only requires that the queue starts holding every node at distance 0, and with k sources that is k nodes rather than one. The first search to reach a cell is by construction the nearest source, because the merged frontier still advances one ring at a time. It is the standard answer to rotting-oranges and nearest-exit grid problems, and it costs one pass instead of k.
A correct Python BFS times out on a large graph. The queue is a list and the code calls `queue.pop(0)`. Why?
Code diagnosis
`pop(0)` shifts every remaining element, so each dequeue is O(queue length) and the run turns quadratic
A list stores elements contiguously, so removing the front element moves everything else down one slot. Over V dequeues that is O(V²) of pure bookkeeping on top of an algorithm that should be linear. The fix is a real deque with O(1) removal from both ends, or an index-into-array queue that never removes at all — the same trap exists for `Array.prototype.shift` in JavaScript.
BFS and DFS are both O(V + E). When is the choice between them not arbitrary?
Comparison
When the answer depends on path length, or when memory is bounded by frontier width versus depth
BFS is the only one of the two that answers "fewest steps", so any shortest-path or minimum-moves question settles the choice immediately. Where both would work — reachability, component counting, cycle detection — the deciding factor is memory shape: BFS pays for the widest level, DFS pays for the deepest path. On a wide shallow graph DFS is cheaper; on a deep narrow one BFS is, and DFS additionally risks a stack overflow.
Every edge in your weighted graph happens to have weight 7. Should you run Dijkstra?
Comparison
No — with uniform weights BFS settles nodes in the same order, and you can multiply hops by 7
Dijkstra earns its priority queue only when different edges cost different amounts; with one uniform weight the cheapest route is always the one with fewest hops. Running BFS and scaling the answer gives the same distances in O(V + E) instead of O((V + E) log V). Recognising the degenerate case is worth more in an interview than reciting the general algorithm, and the same reasoning is what makes 0-1 BFS possible.
Explain BFS to someone who has never programmed. Say it out loud before revealing.
Explain it plainly
Imagine you want to know how many introductions it takes to reach everyone in a company from one person. Start with your one person and ask them to name everyone they know — write "1 introduction" next to each of those names and put them at the back of a queue. Then take whoever has been waiting longest, ask them for their contacts, and write "2" next to anyone whose name is still blank. Keep going, always serving the front of the queue, and every name ends up with the smallest number of introductions that could possibly reach them — because you only ever ask people in the order you heard about them, so nobody gets asked before someone closer to the start. Where the picture breaks: real introductions vary in effort, and this method assumes every one costs exactly the same. The moment some contacts are harder to reach than others you need a different rule, which is picking the cheapest-so-far person next instead of the longest-waiting one.
The test is whether the listener could run the procedure on paper. A strong answer names the waiting line and the "first time you hear about someone is the shortest way" guarantee without jargon, and volunteers where the picture stops being accurate.