A Pattern-Based Guide to Solving Graph Problems

Graph problems often feel harder than they actually are.

The problem is usually not that the algorithm is complicated. The problem is recognizing which graph pattern the problem is hiding.

A problem may never say:

"This is a BFS problem."

Instead, it might say:

Find the minimum number of moves.
Determine whether one person can reach another.
Find all connected groups.
Determine whether courses can be completed.
Find the cheapest way to connect all cities.
Find the shortest route.
Determine whether two nodes belong to the same group.

All of these are graph problems, but they correspond to different patterns.

This guide is designed around one objective:

Learn the patterns well enough that an unfamiliar graph problem becomes recognizable.

1. The Graph Mental Model

A graph is simply:

Graph = Nodes + Edges

For example:

Nodes:

1, 2, 3, 4, 5

Edges:

1-2
1-3
2-4
3-5
4-5

A graph can be:

Undirected

A ---- B

If you can go from A → B, you can also go from B → A.

Directed

A ---> B

You can travel from A to B, but not necessarily from B to A.

Weighted

A --5--> B

The edge has a cost of 5.

Unweighted

A ---- B

Every edge effectively has the same cost.

2. The Most Important Question

Before thinking about DFS, BFS, Dijkstra, Union-Find, etc., ask:

What does a node represent?

Sometimes the nodes are obvious:

cities → nodes
roads → edges

But sometimes the graph is hidden.

For example:

Word Ladder

A node can be:

"hit"
"hot"
"dot"
"dog"
...

An edge means:

These two words can be transformed into each other.

Or in a grid:

0 0 1
0 1 0
1 0 0

Every cell can be treated as a node.

An edge means:

Two cells are adjacent.

This is one of the most important graph skills:

Don't wait for the problem to explicitly give you a graph. Learn to construct the graph mentally.

3. The Graph Pattern Decision Tree

When you encounter a graph problem, start here.

                    GRAPH PROBLEM
                         |
             What is the problem asking?
                         |
        +----------------+----------------+
        |                |                |
     Explore?         Shortest?       Dependency?
        |                |                |
      DFS/BFS             |          Topological Sort
                         |
              +----------+----------+
              |                     |
          Unweighted              Weighted
              |                     |
             BFS             +-------+-------+
                            |               |
                         Positive        0/1 weights
                         weights             |
                            |              0-1 BFS
                         Dijkstra

Another branch:

Need to merge groups?
        |
      DSU

Need minimum cost to connect everything?
        |
     MST
   /     \
Kruskal  Prim

Need to find all possible paths?
        |
 DFS + Backtracking

Need to determine whether a graph can be colored
with two colors?
        |
    Bipartite

Need to detect a cycle?
        |
   +----+----+
   |         |
Undirected Directed
   |         |
 DFS/DSU    DFS/Kahn

The rest of this guide explains these patterns and provides LeetCode problems for practice.

Pattern 1: Graph Representation

Before solving graph problems, you need to be comfortable converting the input into an adjacency list.

Suppose:

edges = [
    [0, 1],
    [0, 2],
    [1, 3]
]

This means:

0 -- 1
|
2
 
1 -- 3

For an undirected graph:

graph = [[] for _ in range(n)]
 
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)

python

Result:

0 → [1, 2]
1 → [0, 3]
2 → [0]
3 → [1]

For a directed graph:

graph = [[] for _ in range(n)]
 
for u, v in edges:
    graph[u].append(v)

python

Result:

0 → [1, 2]
1 → [3]
2 → []
3 → []

Weighted graph

Input:

edges = [
    [0, 1, 5],
    [0, 2, 2],
    [1, 3, 4]
]

Build:

graph = [[] for _ in range(n)]
 
for u, v, weight in edges:
    graph[u].append((v, weight))

python

Now:

0 → [(1,5), (2,2)]
1 → [(3,4)]

The pattern

Whenever you see:

edges
connections
roads
flights
routes
relationships
prerequisites

ask:

Can I convert this into graph[node] = neighbors?

If yes, traversal algorithms become much easier.

Practice Problems

Pattern 2: DFS — Explore Everything Connected

DFS means:

Keep going deeper before coming back.

Consider:

Starting at 0:

0 → 1 → 3
        ↓
        2

A standard DFS:

def dfs(node):
    visited.add(node)
 
    for nei in graph[node]:
        if nei not in visited:
            dfs(nei)

python

Using Stack

class Solution:
    def validPath(
        self,
        n: int,
        edges: List[List[int]],
        source: int,
        destination: int
    ) -> bool:
 
        # 1. Build adjacency list
        adj = [[] for _ in range(n)]
 
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)
 
        # 2. DFS using stack
        visited = [False] * n
        stack = [source]
        visited[source] = True
 
        # 3. Explore graph
        while stack:
            node = stack.pop()
 
            if node == destination:
                return True
 
            for nei in adj[node]:
                if not visited[nei]:
                    visited[nei] = True
                    stack.append(nei)
 
        return False

python

The important part isn't the syntax.

The important invariant is:

When dfs(node) starts, we are exploring the entire region reachable from node.

When should you think DFS?

Look for:

explore
visit
connected
reachable
region
component
island
path
recursively explore
mark all connected nodes

Practice Problems

Example: Number of Islands

Grid:

1 1 0
1 0 0
0 0 1

There are two islands.

Treat every 1 as a node.

Adjacent 1s are connected.

1--1
|
1
 
 
1

So the problem becomes:

How many connected components exist?

DFS:

def dfs(i, j):
    if i < 0 or i >= rows:
        return
 
    if j < 0 or j >= cols:
        return
 
    if grid[i][j] == "0":
        return
 
    grid[i][j] = "0"
 
    dfs(i + 1, j)
    dfs(i - 1, j)
    dfs(i, j + 1)
    dfs(i, j - 1)

python

Then:

count = 0
 
for i in range(rows):
    for j in range(cols):
        if grid[i][j] == "1":
            count += 1
            dfs(i, j)

python

The key insight:

Find every unvisited node
        ↓
Start DFS
        ↓
DFS consumes the entire component
        ↓
Increment answer

This exact idea appears in many problems.

Pattern 3: BFS — Level-by-Level Exploration

BFS explores nodes according to distance from the starting node.

Example:

        0
      /   \
     1     2
    / \     \
   3   4     5

BFS order:

0
1 2
3 4 5

Template:

from collections import deque
 
q = deque([start])
visited = {start}
 
while q:
    node = q.popleft()
 
    for nei in graph[node]:
        if nei not in visited:
            visited.add(nei)
            q.append(nei)

python

Why BFS is so important

In an unweighted graph, BFS finds the shortest number of edges from the source.

Suppose:

A -- B -- C -- D
 \        /
  E ---- F

From A:

distance(A) = 0
distance(B) = 1
distance(E) = 1
distance(C) = 2
distance(F) = 2
distance(D) = 3

BFS naturally processes nodes in increasing distance.

Therefore:

Unweighted shortest path → BFS

Practice Problems

Example: Word Ladder

Suppose:

hit → hot → dot → dog → cog

Every transformation costs exactly one operation.

So:

hit
 ↓
hot
 ↓
dot
 ↓
dog
 ↓
cog

This is an unweighted shortest-path problem.

Therefore:

BFS

The important recognition pattern is:

Every move has the same cost + minimize number of moves → BFS.

Pattern 4: BFS on a Grid

A grid is often just a graph in disguise.

For:

[
 [0, 0, 0],
 [0, 1, 0],
 [0, 0, 0]
]

Each cell is a node.

Neighbors are usually:

directions = [
    (1, 0),
    (-1, 0),
    (0, 1),
    (0, -1)
]

python

Template:

from collections import deque
 
q = deque([(start_i, start_j)])
visited = {(start_i, start_j)}
 
while q:
    i, j = q.popleft()
 
    for di, dj in directions:
        ni = i + di
        nj = j + dj
 
        if not valid(ni, nj):
            continue
 
        if (ni, nj) in visited:
            continue
 
        visited.add((ni, nj))
        q.append((ni, nj))

python

The critical grid insight

Many grid problems are actually:

Graph traversal

Examples:

Problem	Hidden Graph
Number of Islands	Cells
Rotten Oranges	Cells
Shortest Path in Binary Matrix	Cells
Pacific Atlantic Water Flow	Cells
Word Search	Cells + backtracking

When you see:

matrix
grid
cells
up/down/left/right
neighbors

immediately think:

Graph traversal on implicit nodes.

Practice Problems

Pattern 5: Connected Components

This pattern appears constantly.

Suppose:

0 -- 1       2 -- 3
 
4 -- 5

There are three components:

{0,1}
{2,3}
{4,5}

The algorithm:

components = 0
 
for node in range(n):
    if node not in visited:
        components += 1
        dfs(node)

python

The deeper principle is:

One DFS/BFS consumes exactly one connected component.

Practice Problems

Example: Number of Provinces

Given:

isConnected = [
    [1,1,0],
    [1,1,0],
    [0,0,1]
]

Graph:

0 ---- 1
 
2

Answer:

DFS:

def dfs(node):
    visited[node] = True
 
    for nei in range(n):
        if isConnected[node][nei] == 1 and not visited[nei]:
            dfs(nei)

python

Then:

count = 0
 
for node in range(n):
    if not visited[node]:
        count += 1
        dfs(node)

python

Pattern 6: Cycle Detection — Undirected Graph

Suppose:

0 -- 1
|    |
3 -- 2

There is a cycle.

A common DFS technique is:

current node
    |
neighbor
    |
Is neighbor already visited?
    |
   yes
    |
Was neighbor NOT the parent?
    |
   yes
    |
  CYCLE

Template:

def dfs(node, parent):
    visited[node] = True
 
    for nei in graph[node]:
        if not visited[nei]:
            if dfs(nei, node):
                return True
 
        elif nei != parent:
            return True
 
    return False

python

Why do we ignore the parent?

Consider:

0 -- 1

From 0, we visit 1.

At 1, we see 0.

But 0 is simply the node we came from.

That is not a cycle.

Therefore:

elif nei != parent:

python

is critical.

Practice Problems

Alternative: Union-Find for Undirected Cycle Detection

Suppose edges arrive one by one:

0-1
1-2
2-3
3-0

Initially:

{0}
{1}
{2}
{3}

After:

0-1

we have:

{0,1}

After:

1-2

we have:

{0,1,2}

After:

2-3

we have:

{0,1,2,3}

Now process:

3-0

But 3 and 0 already belong to the same component.

Therefore:

cycle!

This is the core idea behind:

Redundant Connection

Pattern 7: Union-Find / DSU

Union-Find is useful when the problem is fundamentally about groups.

It supports two operations:

find(x)

Find which group x belongs to.

union(a, b)

Merge the groups containing a and b.

DSU Template

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
 
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
 
        return self.parent[x]
 
    def union(self, a, b):
        pa = self.find(a)
        pb = self.find(b)
 
        if pa == pb:
            return False
 
        if self.rank[pa] < self.rank[pb]:
            pa, pb = pb, pa
 
        self.parent[pb] = pa
 
        if self.rank[pa] == self.rank[pb]:
            self.rank[pa] += 1
 
        return True

python

When should you think DSU?

Look for:

connect
merge
groups
components
same group
redundant edge
connected after adding edges
dynamic connectivity

Practice Problems

DFS vs BFS vs DSU

This distinction is extremely important.

DFS/BFS

Use when you need to explore the graph.

"Can I reach this node?"
"How many components?"
"What nodes are connected?"

DSU

Use when you need to maintain connectivity while edges are being added or processed.

"Are these already connected?"
"Merge these two groups."
"Does this edge create a cycle?"

Pattern 8: Bipartite Graph

A graph is bipartite if you can divide its nodes into two groups such that:

No edge connects two nodes in the same group.

Example:

Group A       Group B
 
  0 --------- 1
  |           |
  2 --------- 3

Color:

0 → Red
1 → Blue
2 → Blue
3 → Red

Every edge connects different colors.

The Algorithm

Start with an uncolored node.

color[node] = 0

All neighbors become:

Their neighbors become:

And so on.

BFS implementation:

from collections import deque
 
color = [-1] * n
 
def bfs(start):
    q = deque([start])
    color[start] = 0
 
    while q:
        node = q.popleft()
 
        for nei in graph[node]:
            if color[nei] == -1:
                color[nei] = 1 - color[node]
                q.append(nei)
 
            elif color[nei] == color[node]:
                return False
 
    return True

python

Run it for every component.

Recognition Pattern

Think:

Can I divide people into two groups?
 
Can people be assigned to two teams?
 
Can this graph be colored using two colors?
 
No two connected nodes can belong to the same group.

Then think:

Bipartite → 2-coloring → BFS/DFS

Practice Problems

Pattern 9: Directed Graph Cycle Detection

Directed graphs are different.

Consider:

0 → 1 → 2
    ↑   |
    |___|

There is a directed cycle:

1 → 2 → 1

A simple visited set is not enough.

We need to know whether a node is:

currently being explored

Use three states:

0 = unvisited
1 = currently visiting
2 = completely processed

DFS:

state = [0] * n
 
def dfs(node):
    state[node] = 1
 
    for nei in graph[node]:
 
        if state[nei] == 1:
            return True
 
        if state[nei] == 0:
            if dfs(nei):
                return True
 
    state[node] = 2
    return False

python

Why does state == 1 mean cycle?

Suppose:

0 → 1 → 2
    ↑   |
    |___|

DFS path:

Then 2 → 1.

But 1 is currently on our recursion path.

Therefore:

cycle

Practice Problems

Course Schedule

This is one of the most important graph pattern problems.

Suppose:

Course 1 requires Course 0

Represent it as:

0 → 1

If:

0 → 1
1 → 0

then:

0 → 1 → 0

There is a cycle.

Therefore the courses cannot be completed.

The important transformation is:

Prerequisites → Directed graph → Cycle detection

LeetCode describes Course Schedule as a problem of determining whether all courses can be completed given prerequisite relationships.

Pattern 10: Topological Sort

Topological sorting applies to:

Directed Acyclic Graphs (DAGs)

It produces an ordering where:

u → v

means:

u must appear before v

Example:

0 → 2
1 → 2
2 → 3

Possible ordering:

0, 1, 2, 3

Another:

1, 0, 2, 3

Both are valid.

The Most Important Recognition Pattern

Look for:

prerequisites
dependencies
before
after
ordering
schedule
build order
course prerequisites
task dependencies

Then think:

Directed dependency graph → Topological Sort

Practice Problems

Kahn's Algorithm

Kahn's algorithm uses indegree.

Indegree means:

Number of incoming edges.

For:

0 → 2
1 → 2
2 → 3

indegree:

Start with nodes having:

indegree = 0

So:

0, 1

Process them.

When removing:

0 → 2

decrease:

indegree[2]

Eventually 2 becomes zero.

Then process 2.

Kahn Template

from collections import deque
 
indegree = [0] * n
 
for u in range(n):
    for v in graph[u]:
        indegree[v] += 1
 
q = deque()
 
for node in range(n):
    if indegree[node] == 0:
        q.append(node)
 
order = []
 
while q:
    node = q.popleft()
    order.append(node)
 
    for nei in graph[node]:
        indegree[nei] -= 1
 
        if indegree[nei] == 0:
            q.append(nei)

python

Cycle detection:

if len(order) != n:
    return []

python

Why?

Because if a cycle exists:

0 → 1 → 2 → 0

every node has an incoming dependency.

Therefore:

indegree never becomes 0

Topological Sort as a General DP Pattern

This is a very important extension.

Suppose:

A → B → C

and each node has a value.

Sometimes you want:

best answer for B

based on:

best answer for A

Because dependencies form a DAG, you can process nodes in topological order.

This gives a powerful pattern:

DAG
 ↓
Topological order
 ↓
Dynamic Programming

This appears in problems involving:

longest path in a DAG
dependency-based scoring
prerequisite chains
parallel courses

Pattern 11: Shortest Path

Shortest-path problems are not all solved by the same algorithm.

This decision is critical.

Shortest path
     |
     +--------------------------+
     |                          |
Unweighted                  Weighted
     |                          |
    BFS                 +--------+--------+
                       |                 |
                  Positive weights    0/1 weights
                       |                 |
                   Dijkstra          0-1 BFS

There are also cases involving negative weights:

Negative weights
      |
Bellman-Ford

And all-pairs shortest paths:

Every node → every node
      |
Floyd-Warshall

Practice Problems

Unweighted Shortest Path

General Shortest Path

Pattern 12: Dijkstra

Use Dijkstra when:

Edge weights are non-negative.

Example:

A --4-- B
|       |
1       2
|       |
C --5-- D

You want the cheapest distance from A.

Dijkstra repeatedly chooses:

The currently known closest node.

This is why we use a min-heap.

Dijkstra Template

import heapq
 
dist = [float("inf")] * n
dist[start] = 0
 
pq = [(0, start)]
 
while pq:
    distance, node = heapq.heappop(pq)
 
    if distance > dist[node]:
        continue
 
    for nei, weight in graph[node]:
 
        new_distance = distance + weight
 
        if new_distance < dist[nei]:
            dist[nei] = new_distance
            heapq.heappush(pq, (new_distance, nei))

python

The core idea is:

Take closest known node
        ↓
Try improving its neighbors
        ↓
Push improved distances

Why the stale-entry check?

You may push the same node multiple times.

Example:

(10, A)
(5, A)

When (5, A) is processed first:

dist[A] = 5

Later:

(10, A)

is stale.

Therefore:

if distance > dist[node]:
    continue

python

Recognition Pattern

Think Dijkstra when you see:

minimum cost
minimum travel time
cheapest route
shortest weighted path
positive edge costs

and edges have non-negative weights.

Practice Problems

Pattern 13: 0-1 BFS

Sometimes edge weights are only:

0 or 1

Example:

A --0-- B
A --1-- C

Instead of a heap, use a deque.

Rules:

weight = 0
    → push to front
 
weight = 1
    → push to back

Template:

from collections import deque
 
dist = [float("inf")] * n
dist[start] = 0
 
dq = deque([start])
 
while dq:
    node = dq.popleft()
 
    for nei, weight in graph[node]:
 
        new_dist = dist[node] + weight
 
        if new_dist < dist[nei]:
            dist[nei] = new_dist
 
            if weight == 0:
                dq.appendleft(nei)
            else:
                dq.append(nei)

python

Recognition:

Shortest path + edge costs only 0/1 → 0-1 BFS

Practice Problems

Pattern 14: Bellman-Ford

Bellman-Ford is useful when:

Negative edge weights can exist.

For every edge:

u → v with weight w

relax:

dist[v] = min(dist[v], dist[u] + w)

python

Repeat:

V - 1 times

Why?

A shortest simple path can contain at most:

V - 1 edges

Bellman-Ford Pattern

dist = [float("inf")] * n
dist[start] = 0
 
for _ in range(n - 1):
 
    changed = False
 
    for u, v, weight in edges:
 
        if dist[u] == float("inf"):
            continue
 
        if dist[u] + weight < dist[v]:
            dist[v] = dist[u] + weight
            changed = True
 
    if not changed:
        break

python

Bellman-Ford is much less common in interviews than BFS or Dijkstra, but recognizing the negative-weight condition is important.

Practice Problems

Pattern 15: Floyd-Warshall

Suppose you want:

shortest distance between EVERY pair of nodes

Then think:

Floyd-Warshall

The DP idea:

Can going through k improve i → j?

Formula:

dist[i][j] =
    min(
        dist[i][j],
        dist[i][k] + dist[k][j]
    )

Template:

for k in range(n):
    for i in range(n):
        for j in range(n):
            dist[i][j] = min(
                dist[i][j],
                dist[i][k] + dist[k][j]
            )

python

Complexity:

O(V³)

Therefore it is generally useful only when V is relatively small.

Practice Problems

Pattern 16: Minimum Spanning Tree

This is a different problem from shortest path.

This distinction causes many mistakes.

Shortest Path

Question:

What is the cheapest way from A to B?

Minimum Spanning Tree

Question:

What is the cheapest way to connect ALL nodes?

Example:

A -----5----- B
 \           /
  2         3
   \       /
      C

We want a set of edges that:

connects every node
contains no cycle
has minimum total cost

That is an MST.

MST Pattern

Two major algorithms:

MST
 |
 +---- Kruskal
 |
 +---- Prim

Practice Problems

Pattern 17: Kruskal's Algorithm

Kruskal:

Sort edges by weight and keep adding the cheapest edge that doesn't create a cycle.

Example:

A-B = 1
B-C = 2
A-C = 3

Sort:

1, 2, 3

Take:

A-B

Take:

B-C

Now everything is connected.

Don't take:

A-C

because it creates a cycle.

This is why Kruskal naturally works with DSU.

Kruskal Template

edges.sort(key=lambda x: x[2])
 
dsu = DSU(n)
 
cost = 0
edges_used = 0
 
for u, v, weight in edges:
 
    if dsu.union(u, v):
        cost += weight
        edges_used += 1
 
        if edges_used == n - 1:
            break

python

Recognition:

connect all nodes
minimum total cost
roads
cables
network
bridges

Think:

MST

Practice Problems

Pattern 18: Prim's Algorithm

Prim grows one connected tree.

Start from any node:

Look at all edges leaving the current tree.

Choose the cheapest.

Then repeat.

Template:

import heapq
 
visited = set()
pq = [(0, 0)]
 
cost = 0
 
while pq:
 
    weight, node = heapq.heappop(pq)
 
    if node in visited:
        continue
 
    visited.add(node)
    cost += weight
 
    for nei, edge_weight in graph[node]:
        if nei not in visited:
            heapq.heappush(
                pq,
                (edge_weight, nei)
            )

python

Mental model:

Kruskal:
sort all edges
 
Prim:
grow one tree

Practice Problems

Pattern 19: Backtracking on Graphs

Some graph problems ask:

Find ALL possible paths.

This is different from ordinary DFS.

Suppose:

0 → 1 → 3
 \   \
  2 → 3

Possible paths:

0 → 1 → 3
0 → 2 → 3
0 → 1 → 2 → 3

Now we need to explore alternatives.

This is:

DFS + Backtracking

Template

result = []
path = []
 
def dfs(node):
 
    path.append(node)
 
    if node == target:
        result.append(path[:])
        path.pop()
        return
 
    for nei in graph[node]:
        dfs(nei)
 
    path.pop()

python

The key difference:

Normal DFS:
    mark visited permanently
 
Backtracking:
    choose
    explore
    undo choice

Why `path[:]`?

Suppose:

result.append(path)

python

Then every entry points to the same mutable list.

Instead:

result.append(path[:])

python

creates a snapshot.

Recognition Pattern

Think:

all paths
all possible routes
all valid sequences
generate paths
find every way from source to target

Then:

DFS + Backtracking

Practice Problems

Pattern 20: Grid Backtracking

Word Search is a classic example.

Suppose:

A B C
D E F
G H I

You need to find:

"ABE"

You can move:

A → B → E

But you cannot reuse the same cell.

So the pattern becomes:

DFS
+
temporary visited state
+
undo state

Template:

def dfs(i, j, index):
 
    if index == len(word):
        return True
 
    if not valid(i, j):
        return False
 
    if grid[i][j] != word[index]:
        return False
 
    if (i, j) in visited:
        return False
 
    visited.add((i, j))
 
    for di, dj in directions:
        if dfs(i + di, j + dj, index + 1):
            return True
 
    visited.remove((i, j))
 
    return False

python

The crucial line is:

visited.remove((i, j))

python

because another path may need to use this cell.

Practice Problems

Pattern 21: Multi-Source BFS

This is one of the most useful BFS patterns.

Normal BFS:

one source
    ↓
expand outward

Multi-source BFS:

source A ─┐
source B ─┼→ BFS simultaneously
source C ─┘

All sources start at distance:

Then BFS expands from all of them simultaneously.

Example: Rotting Oranges

Suppose:

2 1 1
1 1 0
0 1 1

All rotten oranges are sources.

Put all of them into the queue:

q = deque()
 
for i in range(rows):
    for j in range(cols):
        if grid[i][j] == 2:
            q.append((i, j))

python

Then process level by level.

Each level represents:

one minute

This is the key pattern:

Multiple starting points + minimum time to spread → Multi-source BFS

Other Multi-Source BFS Problems

Look for:

spread
infection
fire
nearest source
distance to nearest 0
simultaneously
minimum time for all

Practice Problems

Pattern 22: Distance / Nearest Source

A very common variation:

Find the distance of every node or cell from the nearest source.

For example:

0 1 1
1 1 1
1 1 0

The 0s are sources.

Start BFS from both:

(0,0)
(2,2)

Then calculate minimum distance.

This is another reason multi-source BFS is powerful.

Instead of running:

BFS from every cell

we run:

one BFS from all sources

Complexity becomes:

O(V + E)

instead of potentially:

O(V(V + E))

Practice Problems

Pattern 23: State-Space BFS

Sometimes a graph node isn't simply:

node

The node is actually:

(node, state)

This is an extremely important LeetCode pattern.

Example:

Shortest path where you are allowed to break one wall.

Your state might be:

(row, col, walls_broken)

So:

(2,3,0)

and:

(2,3,1)

are different states.

Even though they are physically at the same cell.

Why?

Because the future possibilities differ.

If:

walls_broken = 0

you still have your ability.

If:

walls_broken = 1

you don't.

Therefore they cannot share the same visited state.

General State-Space Pattern

Ask:

What information determines my future choices?

That becomes the state.

Examples:

(node, keys)
(node, fuel)
(node, remaining_k)
(row, col, obstacle_breaks)
(node, mask)
(node, parity)

Then BFS operates on states:

q = deque([(start, initial_state)])
visited = {(start, initial_state)}

python

This pattern is one of the biggest jumps from easy to hard graph problems.

Practice Problems

Pattern 24: Graph + Bitmask

Suppose there are a small number of special nodes:

keys
cities
people
tasks

and you need to remember which ones you've visited.

Represent the set with a bitmask.

For example:

0000 → none
0001 → item 0
0011 → items 0 and 1
1011 → items 0,1,3

State:

(node, mask)

This allows BFS/DFS to remember subsets efficiently.

Typical use:

Visit every important node with minimum number of moves.

The state becomes:

(node, mask)

python

and the goal:

mask == (1 << k) - 1

python

This pattern appears in harder graph problems such as:

Shortest Path Visiting All Nodes

Practice Problems

Pattern 25: Eulerian Path / Circuit

This pattern is about:

Using every edge exactly once.

This is different from shortest path.

Example:

A → B → C
↑       |
└───────┘

We want to traverse:

every edge exactly once

Key distinction:

Shortest path
    → optimize distance
 
Hamiltonian path
    → visit every vertex once
 
Eulerian path
    → use every edge once

Eulerian Recognition

Look for:

use every edge
visit every ticket
reconstruct route
each edge exactly once

A famous LeetCode problem:

Reconstruct Itinerary

The solution uses a form of Hierholzer's algorithm.

Core idea:

def dfs(node):
    while graph[node]:
        nei = graph[node].pop()
        dfs(nei)
 
    result.append(node)

python

Then:

result.reverse()

python

The surprising part is:

Add a node after exhausting its outgoing edges.

This is postorder traversal.

Practice Problems

Pattern 26: Strongly Connected Components

This is a more advanced directed-graph pattern.

A strongly connected component (SCC) is a group where:

Every node can reach every other node.

Example:

A → B
↑   ↓
D ← C

All four nodes belong to one SCC.

Common algorithms:

Kosaraju
Tarjan

These are less common in interviews than BFS, DFS, Dijkstra, and DSU, but they are useful when the problem talks about:

mutual reachability
strong connectivity
condensing directed graph
groups in directed graph

Practice Problems

Pattern 27: DAG + Dynamic Programming

A DAG gives us something extremely valuable:

No cycles

Therefore, we can process nodes in dependency order.

Suppose:

0 → 1 → 3
 \       ↑
  → 2 ---

We can topologically sort:

0, 1, 2, 3

Then calculate:

dp[1] using dp[0]
dp[2] using dp[0]
dp[3] using dp[1], dp[2]

General pattern:

order = topological_sort()
 
for u in order:
    for v in graph[u]:
        dp[v] = max(
            dp[v],
            dp[u] + weight
        )

python

This turns many seemingly complicated graph problems into standard DP.

Practice Problems

Pattern 28: Implicit Graphs

Some of the hardest graph problems don't provide edges at all.

For example:

Word Ladder

Input:

"hit"
"hot"
"dot"
"dog"
"cog"

There is no:

edges = [...]

You must determine which states are neighbors.

That means:

State → Node
Valid transition → Edge

This is called an implicit graph.

Examples:

Word Ladder

word → node
one-letter transformation → edge

Sliding puzzle

board configuration → node
one legal move → edge

Chess problems

position → node
legal move → edge

Grid

cell → node
movement → edge

This mental model is extremely useful.

Practice Problems

Pattern 29: The "State Transition" Way of Thinking

For difficult graph problems, stop thinking:

"What algorithm do I know?"

Instead ask:

What is my state, and what transitions are allowed?

For example:

State:
(row, col, keys)
 
Transition:
move up/down/left/right
 
Constraint:
cannot enter wall
 
Goal:
reach target with all keys

Now the problem is simply:

Shortest path over states

Therefore:

BFS

This way of thinking generalizes extremely well.

Practice Problems

Pattern 30: Choosing the Algorithm

Here is the decision table worth memorizing.

Problem characteristic	Pattern
Explore graph	DFS/BFS
Count connected components	DFS/BFS/DSU
Reachability	DFS/BFS
Unweighted shortest path	BFS
Multiple starting points	Multi-source BFS
Shortest path with positive weights	Dijkstra
Edge weights 0/1	0-1 BFS
Negative edge weights	Bellman-Ford
All-pairs shortest path	Floyd-Warshall
Dependencies/order	Topological Sort
Directed cycle	DFS/Kahn
Undirected cycle	DFS/DSU
Two-coloring	Bipartite BFS/DFS
Merge components	DSU
Minimum cost to connect all nodes	MST
All possible paths	DFS + Backtracking
Every edge exactly once	Eulerian
State-dependent shortest path	State-space BFS/Dijkstra
DAG optimization	Topological Sort + DP
Mutual reachability in directed graph	SCC

31. The Most Important Pattern: Read the Question Semantically

Don't memorize:

Problem X = BFS
Problem Y = DFS
Problem Z = Dijkstra

Instead memorize the question being asked.

"Can I reach X?"

Think:

DFS / BFS

Practice:

"How many groups are there?"

Think:

Connected Components

Use:

DFS / BFS / DSU

Practice:

"What is the minimum number of moves?"

Ask:

Are all moves equal cost?

If yes:

BFS

Practice:

"What is the minimum cost?"

Ask:

Are edges weighted?

If yes:

Dijkstra

assuming non-negative weights.

Practice:

"Can I finish all tasks?"

Ask:

Are there dependencies?

Think:

Directed graph
+
Cycle detection / Topological Sort

Practice:

"Give me a valid ordering"

Think:

Topological Sort

Practice:

"Connect everything as cheaply as possible"

Think:

MST

Practice:

"Are these two things already connected?"

Think:

DSU

Practice:

"Can I split nodes into two groups?"

Think:

Bipartite

Practice:

"Find every possible path"

Think:

DFS + Backtracking

Practice:

32. The Universal DFS Template

When you don't know what else to do, start from this mental model:

def dfs(node):
 
    mark node
 
    for neighbor in graph[node]:
 
        if neighbor is valid:
            dfs(neighbor)

python

Then add the requirement.

For connected components:

count += 1
dfs(node)

python

For cycle detection:

track parent

For directed cycles:

track recursion state

For paths:

track path

For backtracking:

undo state

This is much more useful than memorizing five separate DFS implementations.

DFS Practice Set

33. The Universal BFS Template

Start with:

from collections import deque
 
q = deque([start])
visited = {start}
 
while q:
 
    node = q.popleft()
 
    for nei in graph[node]:
 
        if nei not in visited:
 
            visited.add(nei)
            q.append(nei)

python

Then modify it.

For shortest distance:

distance[node]

python

For levels:

for _ in range(len(q)):

python

For multiple sources:

q = deque(all_sources)

python

For state-space:

q = deque([(node, state)])

python

BFS Practice Set

34. BFS Level Pattern

This pattern appears constantly.

steps = 0
 
while q:
 
    for _ in range(len(q)):
 
        node = q.popleft()
 
        # process node
 
    steps += 1

python

Why?

At the beginning of each iteration:

queue = all nodes at current distance

After processing them:

queue = all nodes at next distance

Therefore:

one outer iteration = one BFS level

This is extremely useful for:

minimum number of moves
minimum time
spreading processes
shortest path

Practice Problems

35. The Universal Dijkstra Template

Start with:

heap = [(0, start)]
dist[start] = 0

python

Then:

while heap:
 
    d, node = heappop(heap)
 
    if d != dist[node]:
        continue
 
    for nei, weight in graph[node]:
 
        nd = d + weight
 
        if nd < dist[nei]:
 
            dist[nei] = nd
 
            heappush(heap, (nd, nei))

python

The invariant:

dist[node] is our best known distance.

Dijkstra Practice Set

36. The Universal DSU Template

Remember only this:

find
union

Conceptually:

parent[x]

python

tells you who represents the group.

find(x):

Who is my group's representative?

union(a,b):

Merge their groups.

The critical condition:

if find(a) == find(b):
    # already connected

python

This single condition solves a surprising number of problems.

DSU Practice Set

37. Graph Complexity

For an adjacency-list graph:

V = number of vertices
E = number of edges

DFS:

O(V + E)

BFS:

O(V + E)

Topological Sort:

O(V + E)

DSU:

approximately O(E α(V))

which is effectively linear for practical constraints.

Dijkstra with a binary heap:

O((V + E) log V)

Kruskal:

O(E log E)

because of sorting.

Floyd-Warshall:

O(V³)

38. Common Mistakes

Mistake 1: Forgetting visited

Without:

visited

python

an undirected graph can loop forever.

A → B → A → B → ...

Mistake 2: Marking visited too late in BFS

Prefer:

if nei not in visited:
    visited.add(nei)
    q.append(nei)

python

rather than marking when popped.

Otherwise multiple parents may add the same node.

Mistake 3: Using Dijkstra for unweighted graphs

If every edge costs:

use:

BFS

It is simpler and faster.

Mistake 4: Using BFS for weighted shortest path

Normal BFS minimizes:

number of edges

not:

total weight

Example:

A --100-- B
A --1--- C --1--- B

BFS might prefer:

A → B

because it uses one edge.

But the cheapest path is:

A → C → B
cost = 2

Therefore:

weighted shortest path → Dijkstra

Mistake 5: Confusing shortest path with MST

Shortest path:

A → B

MST:

connect ALL nodes

Completely different objectives.

Mistake 6: Forgetting that grids are graphs

If the problem says:

up
down
left
right
neighbor
adjacent

think:

graph traversal

Mistake 7: Using permanent visited in backtracking

In ordinary traversal:

visited.add(node)

python

and never remove it.

In backtracking:

visited.add(node)
 
explore()
 
visited.remove(node)

python

The difference is fundamental.

39. A Practical LeetCode Recognition Cheat Sheet

When reading the problem, highlight these words.

"Reach"

DFS / BFS

Practice:

"Connected"

DFS / BFS / DSU

Practice:

"Components"

DFS / BFS / DSU

Practice:

"Minimum number of moves"

BFS

Practice:

"Minimum time"

BFS / Multi-source BFS

Practice:

"Cheapest"

Dijkstra / MST

Ask:

one source → one destination?

Then:

Shortest path

Ask:

connect everything?

Then:

MST

Practice:

"Prerequisite"

Topological Sort

Practice:

"Dependency"

Topological Sort

Practice:

"Ordering"

Topological Sort

Practice:

"Cycle"

DFS / DSU / Kahn

Practice:

"Two groups"

Bipartite

Practice:

"Every edge"

Eulerian

Practice:

"All paths"

Backtracking

Practice:

"Keys / state / remaining moves"

State-space graph

Practice:

40. A Better Way to Practice Graphs

Don't solve 100 random graph problems.

Instead, solve problems by pattern.

Stage 1 — Traversal

Learn:

DFS
BFS
Grid DFS
Grid BFS
Connected Components

Practice:

Stage 2 — Graph Properties

Learn:

Cycle Detection
Bipartite

Practice:

Stage 3 — Directed Graphs

Learn:

Directed cycle
Topological Sort
Kahn's Algorithm

Practice:

Stage 4 — Shortest Path

Learn:

BFS
Dijkstra
0-1 BFS
Bellman-Ford

Practice:

Stage 5 — Connectivity

Learn:

DSU

Practice:

Stage 6 — MST

Learn:

Kruskal
Prim

Practice:

Stage 7 — Advanced Graphs

Learn:

State-space BFS
Bitmask BFS
Eulerian Path
SCC
DAG + DP

Practice:

41. The Real Skill: Pattern Recognition

Suppose LeetCode gives you:

There are n cities and some roads connecting them. Determine the minimum cost to connect all cities.

Don't start coding.

Ask:

What is being optimized?

Answer:

total connection cost

Then:

Do I need to connect every node?

Yes.

Therefore:

Minimum Spanning Tree

Then choose:

Kruskal or Prim

Another problem:

Given a grid, find the minimum number of moves from the top-left corner to the bottom-right corner.

Ask:

Is it weighted?

No.

Therefore:

BFS

Another:

You are given courses and prerequisites. Return whether all courses can be completed.

Ask:

Prerequisites = dependencies

Therefore:

Directed graph

Then:

Can dependencies contain a cycle?

Yes.

Therefore:

Cycle detection / Topological Sort

Another:

Given roads being added dynamically, determine whether two cities are connected.

Think:

Groups changing over time

Therefore:

DSU

42. The Graph Problem-Solving Framework

For almost every graph problem, use this checklist.

Step 1 — Identify the nodes

Ask:

What does one node represent?

Could be:

city
person
course
cell
word
state
configuration

Step 2 — Identify the edges

Ask:

When can I move from one node to another?

Examples:

road
friendship
prerequisite
adjacency
word transformation
legal move

Step 3 — Determine direction

Ask:

Can A → B imply B → A?

If yes:

undirected

If no:

directed

Step 4 — Determine edge weights

Ask:

Does every move cost the same?

If yes:

BFS

If no:

weighted shortest path

Step 5 — Determine the objective

Ask:

Explore?
Reach?
Count?
Shortest?
Cheapest?
Order?
Connect?
Generate all paths?
Detect cycle?

Step 6 — Choose the pattern

Explore       → DFS/BFS
 
Shortest      → BFS/Dijkstra
 
Dependencies  → Topological Sort
 
Groups        → DSU
 
Connect all   → MST
 
Two colors    → Bipartite
 
All paths     → Backtracking
 
Every edge    → Eulerian
 
State matters → State-space graph

43. The Most Important Graph Templates to Memorize

You don't need to memorize 30 solutions.

Memorize these core skeletons.

DFS

def dfs(node):
 
    visited.add(node)
 
    for nei in graph[node]:
 
        if nei not in visited:
            dfs(nei)

python

BFS

q = deque([start])
visited = {start}
 
while q:
 
    node = q.popleft()
 
    for nei in graph[node]:
 
        if nei not in visited:
 
            visited.add(nei)
            q.append(nei)

python

Multi-source BFS

q = deque(all_sources)
 
while q:
    ...

python

Topological Sort

indegree = [0] * n
 
for u in range(n):
    for v in graph[u]:
        indegree[v] += 1
 
q = deque(
    node for node in range(n)
    if indegree[node] == 0
)
 
while q:
    node = q.popleft()
 
    for nei in graph[node]:
 
        indegree[nei] -= 1
 
        if indegree[nei] == 0:
            q.append(nei)

python

Dijkstra

dist = [float("inf")] * n
dist[start] = 0
 
pq = [(0, start)]
 
while pq:
 
    d, node = heappop(pq)
 
    if d > dist[node]:
        continue
 
    for nei, weight in graph[node]:
 
        nd = d + weight
 
        if nd < dist[nei]:
 
            dist[nei] = nd
            heappush(pq, (nd, nei))

python

DSU

parent = list(range(n))
 
def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]
 
def union(a, b):
 
    pa = find(a)
    pb = find(b)
 
    if pa == pb:
        return False
 
    parent[pb] = pa
    return True

python

44. Final Mental Model

The goal is not:

"I know DFS."

The goal is:

"I know when DFS is the natural representation of the problem."

Likewise, don't memorize:

Dijkstra code

Memorize:

Single-source shortest path + non-negative weighted edges → Dijkstra.

Don't memorize:

Kahn's algorithm

Memorize:

Directed dependencies + need valid order → Topological Sort.

Don't memorize:

Union-Find code

Memorize:

Dynamic connectivity / merging groups → DSU.

Don't memorize:

BFS template

Memorize:

Unweighted shortest path → BFS.

45. The One-Page Graph Decision Tree

                         GRAPH PROBLEM
                              |
                     What are you asking?
                              |
       +----------------------+----------------------+
       |                      |                      |
   EXPLORE                 SHORTEST               ORDER
       |                      |                      |
    DFS/BFS                   |                 Topological
                              |
                    +---------+---------+
                    |                   |
                Unweighted           Weighted
                    |                   |
                   BFS          +-------+-------+
                                |               |
                            Positive          0/1
                                |               |
                            Dijkstra         0-1 BFS
 
 
       +----------------------+----------------------+
       |                      |                      |
     GROUPS                CONNECT ALL            CYCLE
       |                      |                      |
      DSU                     MST              +-----+-----+
                                          Undirected   Directed
                                             |            |
                                           DFS/DSU     DFS/Kahn
 
 
       +----------------------+----------------------+
       |                      |
    ALL PATHS             TWO GROUPS
       |                      |
 Backtracking             Bipartite
 
 
       +----------------------+----------------------+
       |                      |
   EVERY EDGE            STATE MATTERS
       |                      |
   Eulerian             State-space BFS
                         / Dijkstra

Conclusion

Graph problems become much easier when you stop treating every problem as a completely new problem.

Most LeetCode graph problems are variations of a relatively small number of ideas:

DFS / BFS
Connected Components
Cycle Detection
Bipartite Graph
Topological Sort
Shortest Path
Dijkstra
0-1 BFS
Union-Find
Minimum Spanning Tree
Backtracking
Multi-source BFS
State-space Graphs
Eulerian Path
SCC
DAG + Dynamic Programming

The real progression should be:

Learn the algorithm
        ↓
Understand the invariant
        ↓
Recognize the problem pattern
        ↓
Map the problem into that pattern
        ↓
Implement the template
        ↓
Modify only what the problem requires

If you can do that, you don't need to memorize solutions to hundreds of graph problems.

You need to recognize what the problem is actually asking you to compute.

That is the skill that transfers from one LeetCode problem to the next.