Graphs

Model relationships as nodes and edges, then traverse with BFS (shortest path) or DFS (all paths, connectivity).

When to use

• Connected components
• Shortest path
• Dependency ordering
• Cycle detection
• Minimum spanning tree

When NOT to use

• Simple linear data
• No relationships between elements

Common traps

• Forgetting visited set
• Confusing directed vs undirected
• Not handling disconnected components

Key Invariant

BFS finds shortest unweighted paths; DFS explores all paths — always track visited nodes

Problems (29)

#37Number of Islands

#85Pacific Atlantic Water Flow

#86Surrounded Regions

#169Network Delay Time (Dijkstra)

#170Cheapest Flights Within K Stops

#171Minimum Spanning Tree (Prim's)

#172Kruskal's MST

#173Topological Sort

#174Is Graph Bipartite

#175Graph Valid Tree

#176Minimum Height Trees

#178Evaluate Division

#179Open the Lock

#180Shortest Path in Binary Matrix

#181Rotting Oranges

#182Shortest Bridge

#183All Paths From Source to Target

#184Keys and Rooms

#279Minimum Cost to Connect All Points

#280Path with Maximum Probability

#281Find City With Smallest Number of Neighbors at a Threshold Distance

#40Course Schedule

#105Word Ladder

#106Alien Dictionary

#107Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

#109Course Schedule II

#177Reconstruct Itinerary