Graphs: pattern and problems

Step 1 Understand it

Remember it by
Graph = nodes + edges + a visited set. DFS to explore everything; BFS for the fewest steps.

Watch it happen

AnimationGraphs: flood what is connected; take what is ready

Read the animation as text

Count the islands: groups of land (1) joined up, down, left or right. Scan the grid cell by cell, row by row.
The scan reaches land at (0,0) that nobody has counted: a new island, number 1. Now flood it, so it is never counted again.
Depth-first flood: from each flooded cell, try down, up, right, left. (1,0) is land: it joins island #1.
(1,1) is land too: it joins island #1. Water and cells already flooded stop the flood.
(0,1) is land too: it joins island #1. Water and cells already flooded stop the flood.
The scan reaches land at (2,2) that nobody has counted: a new island, number 2. Now flood it, so it is never counted again.
The scan reaches land at (3,3) that nobody has counted: a new island, number 3. Now flood it, so it is never counted again.
Depth-first flood: from each flooded cell, try down, up, right, left. (3,4) is land: it joins island #3.
Scan finished: 3 islands. Flooded land turns to water, so each cell is visited a constant number of times: O(rows × cols).

The idea

A graph is things (nodes) joined by connections (edges); a grid is a graph where each cell links to its neighbours. Explore with DFS (go deep, a stack or recursion) or BFS (spread out in rings, a queue), always marking visited nodes. Ordering with dependencies is topological sort; 'are these connected?' as edges arrive is union-find.

Picture it

flowchart LR
  S(("start")) --> A(("1 step"))
  S --> B(("1 step"))
  A --> C(("2 steps"))
  B --> D(("2 steps"))
  C --> E(("3 steps"))

BFS explores in rings: everything 1 step away, then 2, then 3. That's why the first time it reaches a node is the shortest route.

Analogy

Exploring a cave system with a map you mark as you go. DFS follows one tunnel to its end before backing up; BFS explores every cave one step away, then two steps, and so on.

Where the analogy breaks

In a cave you'd notice you've been somewhere. Code won't: without a visited set it loops forever around a cycle.

More detail

What it is

A pure Graph is like a roadmap. Unlike Trees (where data strictly flows top-down), Graph nodes (called vertices) can be connected to ANY other node, creating loops, cycles, and massive webs of data! Think of Facebook: You are a node, and your friends are nodes connected to you. There is no 'root' person.

When to use it

When modeling real-world networks (Cities & Roads, Social Networks, the Internet).
When asked to find if two things are connected or grouped together.
When finding the shortest path (in terms of steps, not distance).

How it works

To represent a graph in code, we almost always use an 'Adjacency List' (a HashMap where the key is a node, and the value is a list of its neighbors). To traverse it, we use BFS (finding the shortest path via a Queue) or DFS (exploring deep via Recursion). BUT, because graphs can have loops, you MUST use a visited set to avoid running in circles forever!

Example walkthrough

Input: nodes=[A,B,C], edges=[[A,B], [B,C]] - find if A is connected to C

Build Adjacency List: A->[B], B->[A,C], C->[B].
Start DFS at A. Mark A visited. Neighbors of A is [B].
DFS at B. Mark B visited. Neighbors of B are [A, C]. A is visited, skip. Go to C.
DFS at C. Found target C! Return true.

Result: true

Related patterns

Breadth-First Search (BFS): The only way to guarantee the shortest path in an unweighted graph.

Step 2 Recognise it

Words that signal it

'Islands', 'regions', 'connected', 'flood fill' on a grid
'Shortest path / fewest steps' with equal costs → BFS
'Prerequisites', 'order of tasks', 'dependencies' → topological sort
'Is there a cycle?', 'is this a valid tree?', 'redundant connection' → union-find or DFS

Don't confuse it with

Trees: A tree is a graph with no cycles. If something can be reached two ways, you need a visited set.
2-D Dynamic Programming: Moving only right/down and counting paths or minimum cost → DP. Moving in any direction → graph search.

Gut check

Things connected to other things, and I need to explore, count groups or order them? → graph DFS/BFS.

How to recognise it in an interview

The input gives you edges[][] instead of an array. The prompt talks about 'islands', 'connections', 'components', or 'paths'.

Step 3 The template

The general shape. Adapt it to each problem rather than learning one solution per problem.

python

from collections import deque

def bfs_grid(grid, start):
    rows, cols = len(grid), len(grid[0])
    q = deque([start])
    visited = {start}                  # mark when you ADD, not when you pop
    while q:
        r, c = q.popleft()
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in visited and grid[nr][nc] == '1':
                visited.add((nr, nc))
                q.append((nr, nc))
    return visited

The same template in Java

text

class Solution {
    public boolean validPath(int n, int[][] edges, int start, int end) {
        Map<Integer, List<Integer>> adj = new HashMap<>();
        for (int[] edge : edges) {
            adj.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(edge[1]);
            adj.computeIfAbsent(edge[1], k -> new ArrayList<>()).add(edge[0]);
        }
        Set<Integer> visited = new HashSet<>();
        return dfs(adj, start, end, visited);
    }
    private boolean dfs(Map<Integer, List<Integer>> adj, int curr, int target, Set<Integer> visited) {
        if (curr == target) return true;
        if (!visited.add(curr)) return false; // Found a cycle / already been here!
        for (int neighbor : adj.getOrDefault(curr, new ArrayList<>())) {
            if (dfs(adj, neighbor, target, visited)) return true;
        }
        return false;
    }
}

Union-find

python

parent = list(range(n))

def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]  # path compression
        x = parent[x]
    return x

def union(a, b):
    ra, rb = find(a), find(b)
    if ra == rb:
        return False                   # already connected -> this edge makes a cycle
    parent[ra] = rb
    return True

TimeO(V + E): every node and edge once (O(rows × cols) on a grid)

SpaceO(V)

Common mistakes

Marking a node visited when you pop it instead of when you push it, so it gets queued many times.
Going out of the grid: check 0 <= r < rows and 0 <= c < cols first.
In topological sort, forgetting that leftover nodes (not all taken) mean a cycle.
Forgetting the visited HashSet. You WILL get an infinite loop.
Trying to build an Adjacency Matrix (a 2D Array) instead of an Adjacency List when the graph is sparse. It wastes huge amounts of memory.

Step 4 Watch it run

Two problems, traced step by step exactly as the code runs.

Easy example: Number of Islands (DFS flood fill)

Input: grid = ['11000', '11000', '00100', '00011']

found land at	action	cells flooded	islands
(0,0)	new land → island #1	(0,0), (0,1), (1,0), (1,1)	1
(2,2)	new land → island #2	(2,2)	2
(3,3)	new land → island #3	(3,3), (3,4)	3

Result: 3

Notice: Each time you meet unvisited land, that's a new island; flood-filling it means you'll never count it again.

python

def num_islands(grid):
    rows, cols = len(grid), len(grid[0])
    def sink(r, c):
        if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] != '1':
            return
        grid[r][c] = '0'                     # mark visited
        sink(r + 1, c); sink(r - 1, c); sink(r, c + 1); sink(r, c - 1)
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                sink(r, c)
    return count

Medium example: Course Schedule (topological sort)

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]

step	order so far	queue (ready to take)	effect
start	–	[0]	courses with no prerequisites
take 0	[0]	[1, 2]	unlocked [1, 2]
take 1	[0, 1]	[2]	nothing new unlocked
take 2	[0, 1, 2]	[3]	unlocked [3]
take 3	[0, 1, 2, 3]	empty	nothing new unlocked

Result: True — an order exists: [0, 1, 2, 3]

Notice: Take courses with no remaining prerequisites first. If some courses never become ready, there's a cycle and it's impossible.

python

from collections import deque

def can_finish(num_courses, prerequisites):
    adj = [[] for _ in range(num_courses)]
    indegree = [0] * num_courses
    for course, pre in prerequisites:
        adj[pre].append(course)
        indegree[course] += 1
    q = deque(i for i in range(num_courses) if indegree[i] == 0)
    taken = 0
    while q:
        c = q.popleft()
        taken += 1
        for nxt in adj[c]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                q.append(nxt)
    return taken == num_courses

Graphs

Step 1 Understand it

Watch it happen

The idea

Picture it

Analogy

Where the analogy breaks

What it is

When to use it

How it works

Example walkthrough

Related patterns

Step 2 Recognise it

Words that signal it

Don't confuse it with

Gut check

How to recognise it in an interview

Step 3 The template

Union-find

Common mistakes

Step 4 Watch it run

Easy example: Number of Islands (DFS flood fill)

Medium example: Course Schedule (topological sort)

Step 5 Practise

Medium

Hard

What to say in the interview

Follow-up prep