Skip to main content

🕸️ Graph

Graphs unify trees, grids, social networks, and dependency systems. The two workhorses are BFS and DFS; everything else (shortest path, MST, SCC) is a variation.

This category contains 21 problems. Use the patterns below to recognize what's being asked, then jump to the problem list at the bottom.

🧠 Key Patterns​

  • BFS — Shortest path in unweighted graph. Level-by-level traversal.
  • DFS — Connectivity, cycle detection, topological order, path enumeration.
  • Topological Sort — DAG dependency resolution: Kahn (BFS) or DFS post-order.
  • Union-Find (DSU) — Dynamic connectivity, MST (Kruskal), grouping.
  • Dijkstra / Bellman-Ford — Shortest path with non-negative / negative weights.
  • Bipartite Check — Two-color BFS. Equivalent to: no odd cycle.
  • Grid-as-Graph — Islands, flood fill, walls-and-gates. 4 or 8 directions.

⚠️ Common Pitfalls​

  • Forgetting to mark visited before enqueueing → exponential blowup.
  • Using Dijkstra on graphs with negative weights — undefined behavior.
  • Union-find without path compression OR union-by-rank is O(n)O(n) per op.

📚 Study Resources​

📺 Videos​

📖 Books​

  • Introduction to Algorithms (CLRS) — Ch. 22 (Elementary), Ch. 23–26 (MST, SSSP, APSP)
  • Algorithm Design — Kleinberg & Tardos — Ch. 3

🌐 Articles & References​

💻 All Graph Problems​

Last updated on