Skip to content

Graph Cheatsheet

Use this page when the graph model is mostly clear but the algorithm family still feels ambiguous.

Do Not Use When

  • the graph model itself is still unclear
  • the task is really a tree DP, flow modeling, or DSU structure question, not a generic graph-family choice
  • you need proofs or full algorithm derivations more than a chooser

Choose By Edge Model

Core Families

Core Invariants

  • BFS: first visit gives minimum number of edges in an unweighted graph
  • Dijkstra: settled distances stay optimal when all edge weights are nonnegative
  • 0-1 BFS: deque order stays nondecreasing by distance
  • Bellman-Ford: one more relaxation after n - 1 rounds signals a reachable negative cycle

Retrieval Cues

  • "fewest edges" or "minimum moves" -> start from BFS
  • "weights are only 0 and 1" -> do not jump to Dijkstra first
  • "negative edge" or "check for negative cycle" -> Bellman-Ford family
  • "cheapest transport under capacities" -> Min-Cost Flow hot sheet
  • "each row and each column must be used exactly once, and the score is additive" -> Hungarian hot sheet
  • "each side ranks the other side, and the answer must have no blocking pair" -> Stable Marriage hot sheet
  • "the graph is undirected, odd cycles are allowed, and you still want the largest disjoint edge set" -> General Matching hot sheet
  • "many or all vertex pairs ask for their undirected min cut" -> Gomory-Hu hot sheet
  • "plain max flow is still the model, but you want a height/excess preflow engine rather than Dinic" -> Push-Relabel hot sheet
  • "every edge has both minimum and maximum allowed flow" -> Flow With Lower Bounds hot sheet
  • "remove one road or city and connectivity breaks" -> Low-Link hot sheet
  • "use every road / teleporter exactly once" -> Eulerian hot sheet
  • "every object has two modes and each constraint touches two literals" -> Two-SAT hot sheet
  • "same unlabeled rooted tree shape, child order irrelevant" -> Tree Isomorphism hot sheet
  • "same unrooted tree shape, and the only ambiguity should be one or two centers" -> Tree Isomorphism hot sheet
  • "one rooted subtree" or "all descendants of one node" -> Subtree Queries hot sheet
  • "one query marks a small subset of tree vertices, and only the branch points between them matter" -> Virtual Tree hot sheet
  • "tree paths" -> LCA for ancestor/meet questions, HLD for repeated static path aggregates, Euler flattening for subtree-only aggregation
  • "tree paths, but the split is through one balanced center or one logarithmic ancestor chain" -> Centroid hot sheet
  • "tree paths, but the edges themselves change online" -> Link-Cut Tree hot sheet
  • "link-cut tree still feels mysterious because the auxiliary splay tree is the missing piece" -> Splay Tree hot sheet + Link-Cut Tree hot sheet
  • "the edges change online, but the query is still subtree-shaped on one incident edge" -> Euler Tour Tree hot sheet
  • "same component after many merges" -> maybe DSU, not BFS/DFS
  • "same component after adds and deletes, but all events are known first" -> DSU Rollback hot sheet

Invariants To Keep In Mind

  • shortest-path code only updates parent[v] when dist[v] improves
  • heap Dijkstra must skip stale entries
  • 0-1 BFS keeps deque order nondecreasing by distance
  • Bellman-Ford only gives a valid shortest-path answer when no reachable negative cycle keeps improving the target

Quick Anchors In This Repo

Next Stops