Unit 3.1 · about 4 h
104 / 324Graph modeling, representations and state graphs
Every later unit consumes a graph. A wrong model, such as marking a vertex visited when the state is a word or a cell-plus-keys pair, passes small tests and fails the hidden ones.
- explain
- implement
You can now
- Compare adjacency lists, adjacency matrices, edge lists and implicit neighbor functions by build cost, query cost and memory, and pick the default for sparse traversal.
- Explain directed versus undirected storage, weighted cell shapes and dense-integer versus string vertex IDs.
- Explain when a product-state or time-expanded graph is needed instead of marking the original vertex visited.
Covers
- Vertices, edges, direction, weights and problem-state modeling
- Adjacency lists, matrices, edge lists and implicit graphs
- Product-state and time-expanded graphs
Study, in this order
3 steps
- Graph representationDSA Handbook - graphs
The three representations; Picking the right one; What it actually costs; The variants you will meet (Directed vs undirected, Weighted vs unweighted, Vertex IDs: dense integers vs strings, Implicit graphs, In-edges as easily as out-edges)
- Basic Graph Algorithms, Chapter 5Algorithms - graph chapters
Sections 5.2 Basic Definitions, 5.3 Representations and Examples, 5.4 Data Structures (adjacency lists, adjacency matrices and their comparison), 5.5 Whatever-First Search and 5.7 Graph Reductions: Flood Fill (printed pp. 190-207)
- Breadth-first search: state-space BFS section onlyDSA Handbook - graphs
When the pattern bends: State-space BFS (LC 127, LC 752)
Depth · Read only that section here. The queue mechanics belong to the BFS unit.
Focus on
- Default to the adjacency list on sparse graphs: at \(n = 10^{5}\) the chapter's arithmetic gives about 1.6 MB for the list against about \(10^{10}\) matrix cells. Take the matrix only under \(n \le 500\) with heavy edge tests, and keep the raw edge list for Kruskal and Bellman-Ford.
- An undirected edge is two adjacency entries; a directed edge is one. The directed flag belongs in the constructor, not in the traversal.
- An implicit graph is a neighbor function, not a table: four lines of grid arithmetic or one-letter word mutations replace a 10,000-vertex grid build.
- When the state carries more than the vertex (a word, a lock combination, keys held), the visited mark must sit on the state. Marking the bare vertex merges distinct states.
Reproduce closed-book
[(0,1),(0,2),(1,3),(2,3),(3,4)], assert adj[3] == [1,2,4], then BFS from 0 and report distances {0:0, 1:1, 2:1, 3:2, 4:3}. Then write grid_neighbors(r, c, rows, cols) yielding the four in-bounds neighbors, and state in one sentence why Word Ladder nodes are words rather than positions.Traps
- Forgetting the second push for undirected edges: BFS reaches one side of an edge but not the other, and reports disconnected on a connected input.
- Building an adjacency list for an edge-centric algorithm: Kruskal sorts the input edge list and Bellman-Ford scans it; neither queries neighbors of one vertex, so the build is pure overhead.
- Marking the vertex instead of the state: two paths reaching the same cell with different keys collapse into one visited bit, and the second path is wrongly pruned.
Practice
LeetCode 1971: Find if Path Exists in Graph
Examples 1 and 2 (\(n = 3\) triangle with source 0 and destination 2; two-component graph with source 0 and destination 5)
Build the adjacency list from the edge list, then traverse. Attempt before reading the DSA Handbook 8.0 worked solution, which is the after-attempt reference for the build-then-traverse contract.
Example 1 (begin hit, end cog, six-word list; expected ladder length 5)
Model first: nodes are words, edges are one-letter mutations. BFS over the implicit graph. After-attempt reference is the State-space BFS section of DSA Handbook 8.1.
Self-test
-
List, matrix or edge list for BFS on a sparse graph with \(n = 10^{5}\), and why?
Adjacency list. Traversal costs \(\Theta(V + E)\) on the list against \(\Theta(V^2)\) on the matrix, and the matrix needs about \(10^{10}\) cells at that scale. -
LC 1557 answers with an in-degree array and no adjacency list. What is the general lesson?
Store the minimum structure the algorithm consumes. In-degree-zero detection needs counts, not neighbors. -
Two searches reach grid cell
(2,2), one holding key A and one holding nothing. One visited bit on(2,2): what breaks?The second arrival is skipped although its future differs: the doors it can open are not the same. The visited key must be(cell, keys). -
Why do Kruskal and Bellman-Ford take the edge list as is?
They consume edges in bulk order (by weight, or all of them per pass) and never query the neighbors of one vertex.
Completion criterion
Stop when
Your blank-file script prints adj[3] == [1,2,4] with the distance table above, and you can name the nodes, edges and visited key of a new narrative before writing code.
Leads to
- 3.2 BFS, unweighted shortest paths and connected components Traverse the graphs you model here, with the visited discipline that makes traversal terminate.
- 5.9 Dynamic programming as shortest paths, formulations and limits Meet state graphs again as shortest paths and DP over DAGs.
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.