Pattern 11 of 18 · Search & Graphs

Graphs

Model relationships as nodes and edges; traverse with DFS/BFS and union-find.

A graph models relationships as nodes and edges, which can be directed or undirected, weighted or not. Most graph problems come down to choosing the right traversal — DFS, BFS, or union-find — for what you're trying to find.

Key concepts

  • Adjacency list: the standard graph representation — each node maps to a list of its neighbors.
  • DFS: explore as deep as possible before backtracking; natural with recursion or an explicit stack.
  • BFS: explore level by level with a queue — the go-to for shortest path in an unweighted graph.
  • Union-Find (Disjoint Set): efficiently tracks which nodes are connected — useful for connectivity and cycle detection.

When to use it

  • The problem involves connections between items (islands, courses with prerequisites, friend networks, grids).
  • You need the shortest path in an unweighted graph (BFS) or need to explore every reachable node (DFS).
  • You're asking "are these two things connected?" repeatedly (union-find).

Tips

  • On a grid, treat each cell as a node connected to its neighbors — most grid problems are graph problems in disguise.
  • Always track visited nodes explicitly, or you'll loop forever on cyclic graphs.
  • BFS guarantees the shortest path in an unweighted graph; DFS does not.

Practice problems (13)

Blind 75 (6):

More from Blind 150 (7):

← BacktrackingAdvanced Graphs →

See the full roadmap →