Advanced Graphs — Master Recap and Algorithm Selection Guide

00 — Complete guide (7 patterns, complexity table)
01 — Kruskal MST      → sort edges + Union-Find O(E log E)
02 — Prim MST         → min-heap expansion O(E log V)
03 — Tarjan SCC       → disc/low/stack O(V+E)
04 — Bridges & AP     → disc/low single DFS O(V+E)
05 — Floyd-Warshall   → all-pairs DP O(V³)
06 — Bellman-Ford     → SSSP with negatives O(VE)
07 — A* Search        → heuristic Dijkstra O(E log V)
08 — Topological Sort → Kahn's BFS / DFS 3-color O(V+E)
09 — Dijkstra States  → state-space (node, stops) O(E log V)
10 — Bipartite Check  → BFS 2-coloring O(V+E)
11 — Min Cost Points  → Prim on complete graph O(n²)
12 — Min-Max Path     → binary search + BFS O(E log W)
13 — Count Paths      → Dijkstra + ways[] array
14 — Critical Conns   → Tarjan bridges O(V+E)
15 — Reconstruct Itin → Hierholzer's Eulerian O(E log E)
16 — Swim Rising Water→ Dijkstra on grid O(n² log n)
17 — Longest Path DAG → topo-sort DP O(V+E)
18 — Network Flow     → Edmonds-Karp O(VE²)
19 — Master Recap     → this file

Connect all vertices, min cost?
  → MST (Kruskal if sparse E log E, Prim if dense E log V)

SSSP, non-negative weights?
  → Dijkstra O((V+E) log V)

SSSP, negative weights, detect cycle?
  → Bellman-Ford O(VE)

All-pairs shortest path, V≤500?
  → Floyd-Warshall O(V³)

Strongly connected components?
  → Tarjan O(V+E) or Kosaraju O(V+E)

Bridge / cut vertex detection?
  → Tarjan bridge/AP algorithm O(V+E)

Ordering with dependencies?
  → Topological sort (Kahn's or DFS) O(V+E)

Is graph 2-colorable?
  → BFS bipartite check O(V+E)

Eulerian path (use all edges)?
  → Hierholzer's algorithm O(E log E)

Maximum flow?
  → Edmonds-Karp O(VE²) or Dinic O(V²E)

Path minimising maximum edge?
  → Binary search + BFS or Kruskal-like