Graphs
BFS, DFS, topological sort, shortest paths, MSTs, graph colouring, union-find. The largest topic-coverage part; bridges to Part 9.
- Chapters
- 13
- Hours
- 4
- Difficulty
- Intermediate to Advanced
- 8.0beginner
Graph representation
Three ways to store a graph (adjacency list, adjacency matrix, edge list), the memory math that decides between them, and the default every interview assumes.
- 8.1intermediate
Breadth-first search
Queue, visited set, and the discipline of never enqueuing the same vertex twice. The shortest-path-on-unweighted-edges algorithm, plus its multi-source and grid variants.
- 8.2intermediate
Depth-first search
Five lines that visit on entry and recurse on neighbors, plus the customization knobs (entry hook, exit hook, edge classification) every advanced graph algorithm later in Part 8 turns.
- 8.3intermediate
Connected components and flood fill
Counting and measuring components in a graph or grid: the outer scan that turns plain BFS or DFS into the algorithm.
- 8.4intermediate
Topological sort: Kahn's algorithm
Indegree-driven, queue-based, iterative. Kahn's algorithm flags a cycle by failing to consume every vertex.
- 8.5intermediate
Topological sort: DFS post-order reverse
DFS-based topological sort: three-color recursion, post-order emission, and the algorithms that fall out of the same skeleton — Tarjan's bridges, Hierholzer's Eulerian path, cycle-length detection.
- 8.6intermediate
Cycle detection in graphs
Three-state DFS coloring for directed cycles, parent-aware single-state DFS for undirected, and the bug both halves share when the wrong one is used.
- 8.7intermediate
Bipartite check
Two-color a graph by BFS or DFS. The odd-cycle obstruction, the linear-time check, and the problem family that disguises this question as 'split into two groups'.
- 8.8intermediate
Union-Find: parent forests, path compression, and union by rank
Parent forests, union by rank, path compression, and the inverse-Ackermann amortized bound. The cycle-detection and connected-components problem family it owns.
- 8.9advanced
Dijkstra's shortest-path algorithm
Single-source shortest paths on weighted graphs with non-negative edges: the priority-queue mechanics, the lazy-deletion idiom, and the min-max-path and 0-1 BFS specializations.
- 8.10advanced
Bellman-Ford and negative cycles
V-1 edge relaxations on every edge, an extra Vth pass to detect negative cycles, and the algorithm that handles the negative-edge case Dijkstra silently mis-reports.
- 8.11advanced
Minimum spanning tree: Kruskal's algorithm
Kruskal's algorithm: sort edges by weight, accept each one whose endpoints sit in different components, halt at n-1 edges. The cycle check is union-find; the cost is the sort.
- 8.12advanced
Minimum spanning trees: Prim's algorithm
Prim's algorithm grows a minimum spanning tree from a single start vertex by absorbing the cheapest crossing edge. Same MST as Kruskal, different path; better choice on dense and implicit graphs.