Algorithms from zero
Graphs: build a dependency and routing engine
Reading about graph algorithms is not the same as wiring them into one system that has to pick the right tool per query. Build a small engine that ingests a graph once and then answers ordering, reachability, and shortest-path questions — choosing BFS, Dijkstra, Kahn’s, or union-find as each query demands, and proving each answer.
Turn the unit’s algorithms into one composable engine: choose a representation, implement traversal, ordering, weighted and unweighted shortest paths with path reconstruction, and dynamic connectivity — then verify each on graphs that exercise the failure modes (cycles, negative edges, disconnected components).
Build a graph engine that loads a directed, optionally weighted graph and answers four query types — topological order, unweighted shortest path, weighted shortest path, and dynamic connectivity — each with the correct algorithm and a verifiable result, including correct refusals when an algorithm does not apply.
- A results table: for a chosen source and target, the BFS shortest path (and its edge count) next to the Dijkstra shortest path (and its total cost), with the concrete vertex sequences reconstructed from parent[], not hand-traced.
- The topological sort returns a valid full order on the DAG (every edge points forward in the list, checked programmatically) and correctly refuses with the trapped-vertex set on the cyclic test graph.
- Dijkstra refuses the negative-edge graph with a clear message naming Bellman-Ford, and produces correct distances on the non-negative graph (verified against a hand-worked small example).
- Union-Find answers a scripted sequence of union/connected queries correctly, the component count decrements by exactly one per successful union and stays unchanged on a redundant union, and find is O(1)-ish after compression (show a path length before and after a find).
- A one-paragraph write-up naming, for each of the four query types, which algorithm you used and the single property that made it correct (BFS level order, Dijkstra settle invariant, Kahn leftover-count cycle check, DSU find-root connectivity).
- Add Bellman-Ford as a fifth query path so the engine handles negative edges and reports a negative cycle when one exists; route queries to Dijkstra vs Bellman-Ford automatically based on whether any edge is negative.
- Add a grid mode: treat a 2D grid of open/blocked cells as an implicit graph with 4-directional neighbors and answer fewest-step pathfinding with BFS, reconstructing the route.
- Add Kruskal's minimum spanning tree using your Union-Find to reject cycle-closing edges, and compare its total weight to the original graph.
- Benchmark adjacency list vs adjacency matrix on a sparse and a dense graph for the same neighbor-iteration and edge-lookup workloads, and confirm the crossover matches the O(V + E) vs O(V squared) prediction.
This is the engineering loop behind real graph systems: model the graph once with the representation that fits its density, then route each query to the algorithm whose invariant matches the question — BFS for fewest edges, Dijkstra for non-negative cost, Kahn’s for dependency order, union-find for dynamic connectivity — and refuse cleanly when an algorithm does not apply (negative edges, cycles). Reconstruct concrete paths from parent[] and verify every answer instead of asserting it. Building it once turns the unit’s separate lessons into one decision reflex.