DSA Atlas

Advanced algorithm field guide

Go beyond traversal. Model the structure.

Choose by graph property, query type, and update pattern. Then follow the invariant through a detailed execution flow.

Choose an algorithm ← Return to basics
  • 0advanced templates
  • 4decision flowcharts
  • 2languages
model-first.md
# Do not choose by name alone
goal = identify_objective()
edge_property = inspect_weights()
query_pattern = inspect_updates()

if goal == "connect all cheaply":
    algorithm = "minimum spanning tree"
elif goal == "route capacity":
    algorithm = "maximum flow"

prove_invariant_before_code()

01 · Selection map

Start with the result you must produce

The same graph can require a completely different algorithm when the objective changes.

02 · Detailed flowcharts

Follow the property that changes the answer

Each branch names the deciding condition, the algorithm, and the invariant you must preserve.

Shortest paths

Which path algorithm fits the edge weights?

StartNeed a shortest path?
InspectWhat are the weights?
Negative edgesBellman–FordRelax every edge V−1 times; a later relaxation reveals a negative cycle.
All pairs, small VFloyd–WarshallAfter phase k, distances may use only vertices 0…k as intermediates.
One target + heuristicA*Expand the smallest known cost plus an admissible remaining-cost bound.
Graph structure

Connection cost, components, or failure points?

ObjectiveWhat structure matters?
Cheapest connected backboneKruskal MSTProcess edges by cost; add an edge only when DSU joins two components.
Mutual reachabilityKosaraju SCCFinish-time order exposes source components in the reversed graph.
Critical undirected edgeBridgesAn edge u–v is a bridge when low[v] > discovery[u].
Network flow

Dinic: build, block, repeat

  1. 01Build residual graphAdd forward capacity and a zero-capacity reverse edge.
  2. 02BFS level graphKeep only edges that move one level closer to the sink.
  3. 03DFS blocking flowPush along level-respecting edges until every route is blocked.
  4. 04Update residual capacitySubtract forward flow and add the same amount to the reverse edge.
  5. 05Can BFS reach sink?Yes: repeat. No: the accumulated flow is maximum.
Specialized queries

Static hierarchy, spatial proximity, or dynamic order?

WorkloadWhich operation repeats?
Ancestor / tree pathLCA binary liftingPrecompute every 2ᵏ-th ancestor; lift both nodes from the largest jump down.
Nearest low-dimensional pointKD-treeVisit the near branch first; prune the far branch when its plane cannot improve the best.
Ordered set changesRed-black treeRotations and recoloring preserve black height and prevent consecutive red nodes.

03 · Advanced template library

Study the invariant, then adapt the code

These templates are intentionally separate from the core catalog so the basic practice path stays focused.