Before We Dive Into the 5 Patterns...

Before learning the patterns, let's quickly review the fundamentals.

What is a Graph?

A graph is a collection of nodes (vertices) connected by edges.

Alice ---- Bob
  |          |
Charlie ---- David

• People → Nodes
• Friendships → Edges

Most graph problems ask you to explore connections, find paths, or optimize routes.

Basic Terminology

Types of Graphs

1. Undirected Graph

Edges work in both directions.

A ----- B

Examples:

• Facebook Friendships
• Two-way Roads

2. Directed Graph

Edges have a direction.

A -----> B

Examples:

• Course Schedule
• Instagram Follow

3. Weighted Graph

Every edge has a cost.

A --5--> B

Examples:

• Flights
• Network Delay Time

4. Unweighted Graph

Every edge has the same cost (usually 1).

Examples:

• Number of Islands
• Clone Graph
• Flood Fill

Tree vs Graph

Graph Representation

Adjacency Matrix

• Space: O(V²)
• Fast edge lookup
• Rarely used in interviews

Adjacency List ⭐

adj = [[] for _ in range(n)]

for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)

• Space: O(V + E)
• Used in almost every LeetCode graph problem

Complexity

Pattern 1: Graph Traversal (DFS / BFS)

Use this pattern when you need to explore or visit nodes.

When to Recognize It

Look for phrases like:

• Can you reach node A from node B?
• Visit every connected node.
• Explore all possible paths.
• Count connected regions.
• Traverse the entire graph.

If you see these clues, think DFS or BFS.

Which One Should You Choose?

📈 Complexity

Template (DFS)

def dfs(node):
    visited.add(node)

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

Template (BFS)

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)

✅ Practice Problems

🟢 Easy

• Find if Path Exists in Graph
• Flood Fill
• Find Center of Star Graph
• Keys and Rooms

🟡 Medium

• Number of Provinces
• Number of Islands
• Clone Graph
• Max Area of Island
• Surrounded Regions
• Pacific Atlantic Water Flow
• All Paths From Source to Target

Pattern 2: Connected Components

Use this pattern when you need to count or identify disconnected groups.

🔍 When to Recognize It

Look for phrases like:

• Count the number of groups.
• How many disconnected components are there?
• Find isolated networks.
• Count islands/provinces/clusters.
• Group connected nodes.

If you see these clues, think Connected Components.

How It Works

1. Iterate through every node.
2. If the node is not visited, you've found a new component.
3. Run DFS or BFS to visit all nodes in that component.
4. Increase the component count.
5. Continue until every node is visited.

📈 Complexity

Template

visited = set()
components = 0

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

✅ Common Problems

🟢 Easy

• Find if Path Exists in Graph

🟡 Medium

• Number of Provinces
• Number of Islands
• Max Area of Island
• Count Sub Islands
• Number of Closed Islands
• Surrounded Regions

🔴 Hard

• Making A Large Island

Pattern 3: Shortest Path

Use this pattern when you need to find the minimum distance, cost, or number of moves.

When to Recognize It

Look for phrases like:

• Shortest path
• Minimum distance
• Least cost
• Minimum time
• Fewest moves

If you see these clues, think Shortest Path.

Which Algorithm Should You Use?

📈 Complexity

BFS Template (Unweighted Graph)

from collections import deque

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

while q:
    node, dist = q.popleft()

    if node == target:
        return dist

    for nei in graph[node]:
        if nei not in visited:
            visited.add(nei)
            q.append((nei, dist + 1))

Dijkstra Template

import heapq

pq = [(0, start)]
distance = {start: 0}

while pq:
    dist, node = heapq.heappop(pq)

    if dist > distance[node]:
        continue

    for nei, wt in graph[node]:
        new_dist = dist + wt

        if nei not in distance or new_dist < distance[nei]:
            distance[nei] = new_dist
            heapq.heappush(pq, (new_dist, nei))

Bellman-Ford Template

distance = [float('inf')] * n
distance[src] = 0

for _ in range(n - 1):
    for u, v, wt in edges:
        if distance[u] != float('inf') and distance[u] + wt < distance[v]:
            distance[v] = distance[u] + wt

Floyd-Warshall Template

INF = float('inf')

dist = [[INF] * n for _ in range(n)]

for i in range(n):
    dist[i][i] = 0

for u, v, wt in edges:
    dist[u][v] = wt

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

✅ Common Problems

🟢 Easy

• Shortest Path in Binary Matrix

🟡 Medium

• Network Delay Time
• Path With Minimum Effort
• Minimum Cost to Make at Least One Valid Path in a Grid
• Cheapest Flights Within K Stops

🔴 Hard

• Swim in Rising Water
• The Maze III

Pattern 4: Topological Sort (DAG)

Use this pattern when tasks must be completed in a valid order based on dependencies.

When to Recognize It

Look for phrases like:

• Course prerequisites
• Dependency graph
• Build order
• Task scheduling
• Can I finish all tasks?
• Find a valid ordering

If you see these clues, think Topological Sort.

Which Algorithm Should You Use?

Note: Topological Sort only works on Directed Acyclic Graphs (DAGs).

📈 Complexity

Kahn's Algorithm (BFS)

from collections import deque

indegree = [0] * n

for u in range(n):
    for v in graph[u]:
        indegree[v] += 1

q = deque()

for i in range(n):
    if indegree[i] == 0:
        q.append(i)

order = []

while q:
    node = q.popleft()
    order.append(node)

    for nei in graph[node]:
        indegree[nei] -= 1
        if indegree[nei] == 0:
            q.append(nei)

DFS Topological Sort

visited = set()
order = []

def dfs(node):
    visited.add(node)

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

    order.append(node)

for node in range(n):
    if node not in visited:
        dfs(node)

order.reverse()

✅ Common Problems

🟡 Medium

• Course Schedule
• Course Schedule II
• Parallel Courses

🔴 Hard

• Alien Dictionary
• Sort Items by Groups Respecting Dependencies
• Build a Matrix With Conditions

Pattern 5: Minimum Spanning Tree (MST) & Union-Find (DSU)

Use this pattern when you need to connect all nodes with the minimum total cost or efficiently manage connected components.

When to Recognize It

Look for phrases like:

• Connect all nodes
• Minimum cost to connect
• Remove redundant connections
• Detect cycles
• Merge groups
• Check if two nodes belong to the same component

If you see these clues, think MST or Union-Find (DSU).

Which Algorithm Should You Use?

📈 Complexity

Note: α(N) (Inverse Ackermann Function) grows so slowly that it's practically constant.

Union-Find (DSU) Template

parent = list(range(n))

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(x, y):
    px, py = find(x), find(y)

    if px != py:
        parent[py] = px

Kruskal's Algorithm Template

edges.sort(key=lambda x: x[2])

cost = 0

for u, v, wt in edges:
    if find(u) != find(v):
        union(u, v)
        cost += wt

Prim's Algorithm Template

import heapq

visited = set()
pq = [(0, 0)]   # (weight, node)
cost = 0

while pq:
    wt, node = heapq.heappop(pq)

    if node in visited:
        continue

    visited.add(node)
    cost += wt

    for nei, w in graph[node]:
        if nei not in visited:
            heapq.heappush(pq, (w, nei))

✅ Common Problems

🟡 Medium

• Redundant Connection
• Graph Valid Tree (Premium)
• Number of Connected Components in an Undirected Graph (Premium)

🔴 Hard

• Min Cost to Connect All Points
• Optimize Water Distribution in a Village (Premium)
• Checking Existence of Edge Length Limited Paths

Final Cheat Sheet

## The Decision Tree

Graph Problem?

│

├── Need to explore?
│      → DFS / BFS

├── Need shortest path?
│      → BFS / Dijkstra

├── Need task ordering?
│      → Topological Sort

├── Need minimum cost to connect?
│      → MST

└── Need to merge/check components?
       → Union Find

Final Thoughts

Graph problems can seem overwhelming because there are many algorithms to learn.

Instead of memorizing every algorithm, focus on recognizing the pattern first. Once you identify the pattern, choosing the right algorithm becomes much easier.

If this guide helped you, consider giving it an upvote so it can help more people preparing for coding interviews.

Happy Coding!