Algorithms · Cluster
Graph Traversal
Reachability, connectivity, and traversal order.
- 01 Adjacency Lists, Matrices, and the Cost of Asking Who Is Adjacent How adjacency matrices, per-vertex lists, and compressed sparse row arrays differ in memory, neighbour iteration, and edge lookup, and which graph shapes favour each.
- 02 Why Breadth-First Search Cannot Discover Vertices Out of Distance Order The queue invariant behind BFS distances, why vertices must be marked on enqueue rather than on dequeue, and where the layer argument stops holding.
- 03 Discovery and Finish Times: What DFS Edge Classification Encodes How the two timestamps recorded by depth-first search partition a directed graph into tree, back, forward, and cross edges, and why undirected graphs admit only two of those classes.
- 04 Iterative Depth-First Search Without Losing Finish Times Why a stack of vertices does not reproduce recursive DFS, how to keep an explicit frame with a resume index, and what changes when the traversal can be paused and resumed.
- 05 Labelling Connected Components Once Versus Maintaining Them Under Insertions How a single traversal assigns component identifiers in linear time, why the same problem becomes hard when edges arrive online, and what the two approaches cost on either side of that line.
- 06 Two-Colouring a Graph: Why BFS Decides Bipartiteness and Odd Cycles Do Not The equivalence between bipartite graphs and odd-cycle-free graphs, how a colouring traversal detects the failure in linear time, and what the check does not decide.
- 07 Topological Order From Finish Times and Why the Reverse Is the Answer The finish-time argument that makes reverse post-order a valid topological sort, why the reverse prefix order is not, and how cycle detection folds into the same traversal.
- 08 Lowlink Values: How One DFS Pass Finds Strongly Connected Components Why the minimum reachable discovery index identifies component roots, why edges to finished components must be ignored, and how the output order relates to the condensation.
- 09 Dominator Trees and the Cooper-Harvey-Kennedy Iterative Method What it means for one vertex to dominate another, why the immediate dominator relation forms a tree, and how reverse post-order makes the iterative fixpoint converge quickly.
- 10 Frontier Traversal When the Graph Exceeds Cache: Top-Down Against Bottom-Up Why breadth-first search becomes memory-bound on large graphs, how a bottom-up step inverts the loop over unvisited vertices, and when switching directions pays.