Graph Algorithm Selection Poster

One-page visual decision aid: pick the right graph algorithm in ≤ 30 seconds. Pair with BFS vs DFS Guide for the foundational decision and the graph-foundations chapter for full lessons.

---

Decision Tree by Problem Type

What are you computing?
│
├── Shortest Path
│   ├── Unweighted?
│   │   └─-> BFS                                O(V + E)
│   ├── DAG?  (check this BEFORE looking at edge signs —
│   │         topological order handles negative weights correctly)
│   │   └─-> Topological sort + relax           O(V + E)
│   ├── Non-negative weights?
│   │   ├── Single source -> Dijkstra            O((V+E) log V)
│   │   └── All pairs, V <= 500 -> Floyd-Warshall O(V³)
│   └── Negative weights, not a DAG?
│       ├── Single source -> Bellman-Ford         O(V * E)
│       └── SPFA: same worst case, often faster in practice;
│           Codeforces frequently has anti-SPFA tests, so prefer
│           Bellman-Ford or Johnson's (potentials + Dijkstra)
│           when correctness margin matters.
│
├── Connectivity
│   ├── Static undirected?
│   │   ├── Just connected? -> DFS / BFS / DSU    O(V + E)
│   │   └── Bridges / articulation pts -> Tarjan  O(V + E)
│   ├── Static directed?
│   │   └─-> SCC (Tarjan or Kosaraju)             O(V + E)
│   └── Dynamic (online unions)?
│       └─-> DSU with rank + path compression     O(α(n))
│
├── Minimum Spanning Tree
│   ├── Dense graph (E ~= V²)?
│   │   └─-> Prim (adjacency matrix)              O(V²)
│   └── Sparse graph?
│       ├── Kruskal (sort edges + DSU)            O(E log E)
│       └── Prim + priority queue                 O((V+E) log V)
│
├── Cycles
│   ├── Directed graph?
│   │   └─-> DFS with coloring (white/gray/black) O(V + E)
│   └── Undirected graph?
│       └─-> DFS with parent tracking / DSU        O(V + E)
│
├── Topological Sort
│   └─-> DFS (reverse postorder) or Kahn's BFS    O(V + E)
│
├── Network Flow / Matching
│   ├── Max flow?
│   │   ├── Small graph -> Ford-Fulkerson / Edmonds-Karp  O(V * E²)
│   │   └── Large graph -> Dinic's algorithm              O(V² * E)
│   ├── Min-cost max-flow?
│   │   ├── SPFA-based MCMF — simple, but worst-case risky    O(V * E * flow)
│   │   └── Potentials + Dijkstra (Johnson's-style) MCMF —
│   │       robust against adversarial inputs                   O(flow * (V+E) log V)
│   ├── Bipartite matching?
│   │   ├── Unweighted -> Kuhn's (Hungarian alt.)          O(V * E)
│   │   └── Weighted -> Hungarian algorithm                 O(V³)
│   └── General matching?
│       └─-> Blossom algorithm                              O(V³)
│
└── Tree Queries
    ├── LCA?
    │   ├── O(1) query -> Euler tour + sparse table
    │   └── O(log n) query -> Binary lifting
    ├── Path queries?
    │   └─-> HLD (Heavy-Light Decomposition)       O(log² n)
    ├── Subtree queries?
    │   └─-> Euler tour + BIT/Seg Tree              O(log n)
    └── Distance queries?
        └─-> Centroid Decomposition                 O(log n) per query

---

Algorithm x Complexity Comparison

Algorithm              Time             Space       Key constraint
───────────────────────────────────────────────────────────────────
BFS                    O(V+E)           O(V+E)      unweighted
Dijkstra               O((V+E)lg V)     O(V+E)      no negative edges
Bellman-Ford           O(VE)            O(V)         handles neg edges
Floyd-Warshall         O(V³)            O(V²)        all-pairs, V<=500
Kruskal                O(E lg E)        O(V+E)       MST, sparse
Prim (heap)            O((V+E)lg V)     O(V+E)       MST, sparse
Tarjan (SCC)           O(V+E)           O(V+E)       strongly connected
Tarjan (bridges)       O(V+E)           O(V+E)       bridge finding
Dinic                  O(V²E)           O(V+E)       max flow
Kuhn                   O(VE)            O(V+E)       bipartite matching
Binary lifting         O(n lg n / lg n) O(n lg n)    LCA, k-th ancestor
HLD                    O(n lg² n)       O(n)         path queries
Centroid decomp        O(n lg n)        O(n lg n)    tree distance

lg = log₂ n.

---

See also: 08-bfs-vs-dfs-guide.md for BFS vs DFS decision making.