Adjacency, traversal, and connectivity. Work through the operation contract, runnable case, and cost before selecting the structure for a real workload.
Lessons
- Graphs: adjacency lists and breadth-first reachability
- Disjoint sets: merge connectivity without tracing every path
Practice and next steps
- Project: choose structures for a dispatch board
- Project: audit depot connectivity and daily ranges
- Linear and hash structure decisions
- Tree, graph, and range structure decisions
- DSA Tutorial
CSR graphs: pack sparse neighbors for repeated scans
Dependency graphs: topological order and cycle rejection
Disjoint-set rollback: restore an earlier connectivity checkpoint
Shortest routes: skip stale min-heap entries
Offline connectivity: edge lifetimes and rollback unions
Online connectivity: answer after each edge change
Dense graph bitsets: adjacency and common neighbors
Parity disjoint set: maintain same-or-different constraints
Link-cut forests: change tree edges and sum a path
Potential disjoint sets: preserve numeric differences across merges
Centroid decomposition: nearest marked depot on a fixed tree
CSR delta overlays: stage road edits before compaction
Reachability bitsets: precompute directed paths for a fixed graph
Condensation DAGs: compress directed cycles before path queries
Moveable disjoint sets: transfer one shipment without splitting its old tree
Block-cut indexes: separate articulation depots from cyclic road blocks
Kruskal reconstruction trees: answer route bottlenecks through merge ancestors
De Bruijn graphs: compact non-branching k-mer routes into unitigs