Unit 3.2 · about 4 h
105 / 324BFS, unweighted shortest paths and connected components
BFS is the shortest-path algorithm for uniform cost and the reachability engine for grids. The visited timing, not the queue, is what keeps it linear.
- derive
- implement
You can now
- Prove BFS returns unweighted shortest paths from the layer invariant, and derive the \(\Theta(V + E)\) bound from visited-at-enqueue.
- Implement single-source and multi-source BFS on explicit and grid graphs, with the depth convention stated per problem.
- Turn any traversal into component counting or measuring with an outer scan, on grids and on adjacency matrices.
Covers
- BFS frontier invariant and unweighted shortest paths
- Connected components and reachability
Study, in this order
4 steps
- Breadth-first searchDSA Handbook - graphs
The contract; Why graphs need a visited set when trees don't; The canonical implementation (LC 994); Walking minutes 0 to 3; Multi-source BFS; Two pitfalls that bite
Depth · Skip the 0-1 BFS subsection; it returns in the weighted-shortest-paths unit.
- Connected components and flood fillDSA Handbook - graphs
Why the obvious approach is half an algorithm; The pattern (LC 200); The graph-shape-agnostic reveal: LC 547; Measuring instead of counting: LC 695
Depth · Skip the Union-Find subsection and LC 305; online components belong to the union-find unit.
- Whatever-First Search and disconnected graphsAlgorithms - graph chapters
Sections 5.5 Whatever-First Search and 5.6 Important Variants: the queue variant, disconnected graphs and directed graphs (printed pp. 199-205)
- Unweighted shortest paths by BFSAlgorithms - graph chapters
Chapter 8, Section 8.4 Unweighted Graphs: Breadth-First Search with the FIFO queue and layer analysis (printed pp. 278-281)
Focus on
- Mark visited at enqueue, on the same line as the push. Marking at dequeue lets several queued neighbors push the same vertex, so the queue holds up to \(E\) entries, and without a skip-on-pop check each duplicate is expanded again, up to \(\Theta(V \times E)\) work on dense graphs.
- The FIFO invariant: the queue always holds vertices at most two consecutive distances from the sources. Draining a full layer before the next is what makes first discovery shortest.
- Multi-source BFS seeds every source at depth 0 in one pre-scan, equivalent to a virtual super-source with zero-weight edges. One run replaces one BFS per source.
- Counting is an outer scan wrapped around the traversal: every unvisited land cell starts one flood. Minutes count edges traversed; binary-matrix path length counts cells, so it adds one.
Reproduce closed-book
[[2,1,1],[1,1,0],[0,1,1]] and return 4; on [[2,1,1],[0,1,1],[1,0,1]] return -1; on a grid with no fresh cells return 0. State the input size (\(3 \times 3\)) and that the answer counts edges, not cells.Traps
list.pop(0)as a queue: each pop shifts the remaining elements, so at 20,000 queued cells one pop costs about 1.9 us against about 11 ns fordeque.popleft(measured on 12th Gen i9-12900K, Python 3.13.14). Always importdeque.- A single-source loop over sources for a multi-source question: \(n\) runs give \(n\) single-source distances, not the parallel-frontier minimum the problem asks for.
- Cell-versus-edge counting: LC 994 returns the depth of the last rotted cell while LC 1091 returns depth plus one for the cell-inclusive path. Trace a 3-cell line by hand before submitting.
Practice
LeetCode 200: Number of Islands
Examples 1 and 2 (answers 1 and 3 on the two listed grids)
Attempt cold per the AlgoMaster pool note. After-attempt reference is DSA Handbook 8.3 (LC 200 pattern and LC 547 reveal). Implement iterative BFS: recursive DFS on a \(300 \times 300\) all-land grid recurses about 90,000 deep against the default limit of 1000.
The three listed examples ([[2,1,1],[1,1,0],[0,1,1]] answers 4; the walled-off grid answers -1; [[0,2]] answers 0 because no fresh orange remains)
After-attempt reference is the DSA Handbook 8.1 canonical implementation. State whether you used depth-tagged or layer-counted minutes and keep one style.
Self-test
-
Prove BFS first discovery is shortest.
Induction on layers: sources are distance 0, and the queue dequeues every distance-\(d\) vertex before any distance-\((d + 1)\) vertex is discovered, since discovery appends to the back. So the first edge reaching \(v\) comes from a distance-\((\operatorname{dist}(v) - 1)\) vertex along a shortest path, and no shorter path can exist or \(v\) would have been discovered earlier. -
Why does the super-source argument preserve the bound?
The virtual source adds one vertex and one zero-weight edge per real source, scanned once in the seed pass. Total work stays \(\Theta(V + E)\). -
A diamond \(A \to B\), \(A \to C\), \(B \to D\), \(C \to D\) with visited marked at dequeue: what happens?
\(B\) and \(C\) both see \(D\) unmarked before \(D\) is dequeued, so \(D\) is pushed twice. If the pop skips marked vertices, the answer is still right but the queue carries duplicates; if it does not, \(D\) is expanded twice. Marking at enqueue pushes \(D\) once. -
LC 547 reads an \(n \times n\) matrix but runs the same template as LC 200. What changes?
Only the neighbor function: neighbors of \(i\) are columns \(j\) withisConnected[i][j] == 1. Cost becomes \(\Theta(n^2)\) because every matrix cell is read.
Completion criterion
Stop when
Your blank-file BFS prints 4, -1 and 0 on the three reproduce grids, and you solve LC 200 and LC 994 without changing queue style mid-function.
Mark passed, then open 3.3 Only mark this when you can do it without notes.Leads to
- 3.3 DFS, cycle detection and bipartite testing Swap the queue for a stack and trade the layer guarantee for recursion structure: entry hooks, exit hooks and back edges.
- 3.6 Dijkstra, Bellman-Ford and negative cycles Replace the FIFO with a heap when edges stop costing the same.
Comes after
- 3.1 Graph modeling, representations and state graphsTraverse the graphs you model here, with the visited discipline that makes traversal terminate.
Resources for this unit
- DSA Handbook - graphs Study all of Part 8 in order. For each algorithm, write the representation, invariant, forbidden input assumptions and independently checkable output before reading the implementation.
- Algorithms - graph chapters Use the basic graph, depth-first search, minimum spanning tree, shortest path and flow chapters, and lecture note 11 Disjoint Sets for union-find, for correctness proofs and counterexamples to tempting wrong algorithms.
Also in this section
- AlgoMaster DSA - graph slice Attempt Number of Islands, Course Schedule II and Network Delay Time cold. They cover traversal, dependency modeling and weighted shortest paths; add one narrative problem only if graph modeling remains weak.
- Hypothesis - generated graph tests Generate small sparse, dense, disconnected, cyclic, parallel-edge and weighted graphs. Compare optimized results with exhaustive or deliberately simple references and retain shrunk failures.
- NeetCode - unseen graph problems Use two unseen story problems without graph tags. Grade the model, assumptions, certificate and tests as well as the final answer.