CORE PATTERNVery High Frequency

Graphs

A graph is a set of nodes (vertices) connected by edges. Unlike trees, graphs can have cycles, disconnected components, and edges with weights or directions. Core algorithms — DFS, BFS, Union-Find, Dijkstra, and topological sort — cover virtually every graph problem encountered in interviews.

TimeO(V + E)

SpaceO(V + E)

DifficultyMedium to Hard

Key Insight

Model the problem as a graph, then choose DFS, BFS, or shortest path.

Flip ⟲

Flip for Infographic

Interactive infographic on the flip side.

Click anywhere to Flip ⟲

FLIP SIDEGraphs

Click anywhere to flip back ⟲

Recognition Signals (When to use this pattern)

→Islands, regions, or connected components in a grid or graph
→Shortest path between two nodes (weighted or unweighted)
→Detect a cycle in a directed or undirected graph
→Topological ordering of tasks with dependencies
→Union-Find / dynamic connectivity queries
→Minimum spanning tree or network cost

Types of Problems (Subpatterns)

Each subpattern solves a specific type of problem. Click on a card to view its template.

Graph DFS

Explore as deep as possible from each unvisited node — mark visited to avoid revisiting.

Common Problems

• Number of Islands
• Max Area of Island
• Clone Graph
• Pacific Atlantic Water Flow
• Surrounded Regions

5 problems

Graph BFS — Shortest Path

BFS explores layer by layer — the first time you reach a node is via the shortest path.

Common Problems

• Shortest Path in Binary Matrix
• Rotting Oranges
• Word Ladder
• Minimum Jumps to Reach End
• 01 Matrix

5 problems

Union-Find (DSU)

Track connected components dynamically — union in O(α) amortized with path compression + rank.

Common Problems

• Number of Connected Components in an Undirected Graph
• Redundant Connection
• Graph Valid Tree
• Accounts Merge
• Minimum Spanning Tree (Kruskal's)

5 problems

Topological Sort

Order nodes so all directed edges point forward — use Kahn's BFS or DFS post-order.

Common Problems

• Course Schedule
• Course Schedule II
• Alien Dictionary
• Minimum Height Trees
• Sequence Reconstruction

5 problems

Dijkstra's Algorithm

Greedy shortest path for non-negative edge weights — min-heap drives expansion in order of distance.

Common Problems

• Network Delay Time
• Path With Minimum Effort
• Cheapest Flights Within K Stops
• Find the City With the Smallest Number of Neighbours
• Path With Maximum Probability

5 problems

Cycle Detection

Undirected: parent tracking. Directed: three-colour DFS (white/grey/black).

Common Problems

• Course Schedule (detect cycle in directed graph)
• Graph Valid Tree (undirected, no cycle)
• Redundant Connection
• Find Eventual Safe States
• Detect Cycle in Directed Graph

5 problems

Minimum Spanning Tree

Connect all nodes with minimum total edge weight — Kruskal (DSU) or Prim (heap).

Common Problems

• Minimum Cost to Connect All Points
• Min Cost to Connect Ropes
• Optimize Water Distribution in a Village
• Connecting Cities With Minimum Cost
• Find Critical and Pseudo-Critical Edges in MST

5 problems

Template / Approach

Template for: Graph DFS

Build Adjacency List

Represent the graph as unordered_map<int, vector<int>> or a 2D vector. For grids, neighbours are the 4 (or 8) adjacent cells.

Track Visited

Keep a visited array or set. Mark a node visited before recursing into its neighbours — prevents infinite loops in cyclic graphs.

DFS Each Component

Iterate every node; if unvisited, call dfs(node). This ensures all disconnected components are explored.

template_cpp

💡 Graph DFS skeleton for adjacency-list graphs. For grid DFS, replace the adjacency list with 4-directional neighbour generation and use (row, col) as the visited key.

1// Graph DFS — adjacency list, O(V + E)
2vector<vector<int>> adj;   // adj[u] = list of neighbours of u
3vector<bool> visited;
4 
5void dfs(int node)
6{
7   visited[node] = true;
8 
9   for (int neighbour : adj[node])
10   {
11      if (!visited[neighbour])
12      {
13         dfs(neighbour);
14      }
15   }
16}
17 
18// Call for every unvisited node to handle disconnected components
19int countComponents(int n)
20{
21   adj.assign(n, {});
22   visited.assign(n, false);
23   int components = 0;
24 
25   for (int i = 0; i < n; i++)
26   {
27      if (!visited[i])
28      {
29         dfs(i);
30         components++;
31      }
32   }
33 
34   return components;
35}

Key Idea:Mark visited before recursing (not after) to handle cycles. For grids, sinking visited cells (setting to '0') avoids a separate visited array. For disconnected graphs, always loop over all nodes and call DFS on each unvisited one.

Practice Problems

Sharpen your skills with hand-picked problems.

View All Problems

Medium

Number of Islands

LeetCode #200

Medium

Max Area of Island

LeetCode #695

Medium

Clone Graph

LeetCode #133

Medium

Pacific Atlantic Water Flow

LeetCode #417

Medium

Surrounded Regions

LeetCode #130

Medium

Shortest Path in Binary Matrix

LeetCode #1091

Medium

Rotting Oranges

LeetCode #994

Hard

Word Ladder

LeetCode #127

Medium

01 Matrix

LeetCode #542

Medium

Jump Game III

LeetCode #1306

Medium

Number of Connected Components in an Undirected Graph

LeetCode #323

Medium

Redundant Connection

LeetCode #684

Medium

Graph Valid Tree

LeetCode #261

Medium

Accounts Merge

LeetCode #721

Medium

Course Schedule

LeetCode #207

Medium

Course Schedule II

LeetCode #210

Hard

Alien Dictionary

LeetCode #269

Medium

Minimum Height Trees

LeetCode #310

Medium

Network Delay Time

LeetCode #743

Medium

Path With Minimum Effort

LeetCode #1631

Medium

Cheapest Flights Within K Stops

LeetCode #787

Medium

Path With Maximum Probability

LeetCode #1514

Medium

Find Eventual Safe States

LeetCode #802

Medium

Detect Cycle in Directed Graph

LeetCode #207

Medium

Minimum Cost to Connect All Points

LeetCode #1584

Hard

Optimize Water Distribution in a Village

LeetCode #1168

Hard

Find Critical and Pseudo-Critical Edges in MST

LeetCode #1489

1// Graph DFS — adjacency list, O(V + E)

2vector<vector<int>> adj; // adj[u] = list of neighbours of u

3vector<bool> visited;

5void dfs(int node)

7 visited[node] = true;

9 for (int neighbour : adj[node])

10 {

11 if (!visited[neighbour])

12 {

13 dfs(neighbour);

14 }

15 }

16}

18// Call for every unvisited node to handle disconnected components

19int countComponents(int n)

20{

21 adj.assign(n, {});

22 visited.assign(n, false);

23 int components = 0;

25 for (int i = 0; i < n; i++)

26 {

27 if (!visited[i])

28 {

29 dfs(i);

30 components++;

31 }

32 }

34 return components;

35}