Section 3 of 5 · Algorithms & Data Structures

Graph Modeling & Algorithms

Many scheduling, dependency, routing and state-transition problems are graphs before they are algorithms. Correct modeling and assumption checks matter more than recalling a traversal name.

9 units 18 topics 0/9

Units

9 in this section

3.1 Graph modeling, representations and state graphs
explain · implement
4 h
3.2 BFS, unweighted shortest paths and connected components
derive · implement
4 h
3.3 DFS, cycle detection and bipartite testing
derive · implement
4 h
3.4 Topological ordering and strongly connected components
derive · implement
4 h
3.5 Union-find with path compression and union by rank
implement
3 h
3.6 Dijkstra, Bellman-Ford and negative cycles
derive · implement
5 h
3.7 Minimum spanning trees with Kruskal and Prim
derive · implement
4 h
3.8 Graph certificates and exhaustive small-graph validation
implement · measure
3 h
3.9 Flow and matching at recognition depth
explain
2 h

Before moving on

Checkpoint

Convert two unfamiliar narratives into graphs, implement the selected algorithms with certificates, and reject one wrong method using a minimized counterexample.

Deliberately out of scope

Leave for later

Full maximum-flow and matching implementation families
Spectral and geometric graph algorithms
Large-scale graph processing frameworks

Resources for this section

Shared by every unit above

DSA Handbook - graphs
Handbook Academycourse

primary

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.
AlgoMaster DSA - graph slice
AlgoMasterpractice

required

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.
Algorithms - graph chapters
Jeff Ericksontheory

required

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.
Hypothesis - generated graph tests
Hypothesispractice

support

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
NeetCodeassessment

optional

Use two unseen story problems without graph tags. Grade the model, assumptions, certificate and tests as well as the final answer.

Apply the section

Mini-project · Union-find, two narratives as graphs and a refuted method (10 to 14 h)

Build a tested union-find and turn two unfamiliar narratives into graphs whose algorithms return checkable certificates. Refuting one plausible method with a minimized counterexample trains the modeling judgment the capstone needs.

Steps

Implement union-find with union by rank and path compression. State its invariants and amortized cost, and test it with a Hypothesis state machine against a component-labeling oracle over the unions so far.
Model the AlgoMaster Alien Dictionary narrative as a graph of letters and first-difference edges, treating a longer word before its prefix as invalid. Ship a certificate with every answer: a forward-edge check for an order, or the cycle or bad pair for an empty one.
Test the dictionary solver on generated inputs: draw a random alphabet order, generate words sorted by it, and check outputs against the extracted edges, since several orders can be valid. Add cyclic and bad-prefix cases.
Model LC 1631 Path With Minimum Effort as cells joined by edges weighted by height difference, with path cost as the maximum edge. Solve it with a Dijkstra variant that returns the path and a cut certificate showing the target unreachable below the answer.
Solve LC 1631 a second way with union-find, adding edges in increasing weight until the corners connect. Assert both methods agree on random grids.
Refute a right-and-down-only dynamic program for LC 1631 with Hypothesis against an exhaustive path search, keeping the shrunk counterexample. State the movement assumption that fails.

Deliverables

The union-find module with invariants, cost notes and the state machine.
The Alien Dictionary solver with its certificate checker and generated tests.
Two LC 1631 solutions with the cut certificate, the agreement test and the refutation write-up.

Checks

rubric · Self-grade with the rubric below
external-tests · LeetCode 1631: Path With Minimum Effort

Rubric

Criterion	Pass	Strong
Union-find correctness	The state machine agrees with the component oracle, and the rank-size invariant holds after every step.	Tree heights are measured with and without path compression on an adversarial union order and compared against the bound.
Graph modeling	Each narrative has a written model of vertices, edges, weights and the question asked, stated before code.	The write-up names one modeling alternative that fails and why.
Answer certificates	Every answer ships with a checker that validates it without trusting the solver.	The checker catches a seeded solver bug that the worked examples miss.
Method refutation	The restricted dynamic program is refuted with a minimized counterexample from the exhaustive search.	The write-up states the failed movement assumption and why a shortest-path method repairs it.

Feeds into: Capstone correctness library: union-find and one graph routine, the LC 1631 Dijkstra variant with its certificate. Failure evidence: the refuted method.