Graphs
On this page
Course prerequisites, friend networks, flight routes, a maze, a grid of islands: whenever things are connected to other things in arbitrary ways, neither a list nor a tree fits. Interviewers love these problems because the hard part is rarely the algorithm. It's seeing that the problem is a graph, choosing how to store it, and not visiting the same node twice.
How it works
Nodes and edges
A graph is a set of nodes (also called vertices) and edges between them. Two questions describe any graph:
- Directed or undirected? "A follows B" is directed; "A and B are friends" is undirected. Prerequisites are directed: you must take A before B.
- Weighted or not? Road distances and flight prices are weights. Without weights, every edge counts as one step.
A tree is a special graph: connected, with no cycles. Graphs can have cycles, so every traversal must remember which nodes it has already visited.
Storing a graph: the adjacency list

Most interview problems give you an edge list like [[0, 1], [0, 2], [1, 3]] and you build an adjacency list: for each node, the list of its neighbours. It uses O(V + E) memory (V nodes, E edges), and listing a node's neighbours costs only as much as it has.
An adjacency matrix (matrix[a][b] = 1 if there's an edge) answers "is there an edge from a to b?" in O(1) but always uses O(V²) memory. Use it only for small, dense graphs.
Grids are graphs too

A 2D grid is an implicit graph: cell (r, c) connects to (r−1, c), (r+1, c), (r, c−1) and (r, c+1). You never build an adjacency list; you loop over four direction offsets and skip cells outside the grid or blocked by a wall. Islands, flood fill, rotting oranges and shortest paths in a maze are all grid graphs.
Two ways to explore

- Breadth-first search (BFS) uses a queue and visits nodes in order of distance from the start. In an unweighted graph, the first time BFS reaches a node is along a shortest path.
- Depth-first search (DFS) uses recursion or a stack and follows one path as deep as possible, then backtracks. It's the natural fit for "explore everything connected to this", cycle detection and topological sorting.
Both visit each node and edge once: O(V + E).
Operations and costs
| Task | Tool | Cost |
|---|---|---|
| Visit everything reachable | BFS or DFS | O(V + E) |
| Count connected groups | DFS from every unvisited node, or union-find | O(V + E) |
| Shortest path, every edge costs 1 | BFS | O(V + E) |
| Shortest path, non-negative weights | Dijkstra with a min-heap | O((V + E) log V) |
| Order tasks with dependencies | Topological sort | O(V + E) |
| Detect a cycle | DFS with three colours (directed), or union-find (undirected) | O(V + E) |
When to reach for it
Listen for these clues:
- "Connected", "reachable", "groups", "islands", "regions": DFS or BFS from each unvisited node, counting how many times you start.
- "Minimum number of steps", "shortest", "nearest": BFS when steps cost the same; Dijkstra when they have weights.
- "Prerequisites", "order", "before", "dependencies": a directed graph and a topological sort.
- "Spread at the same time from several places": multi-source BFS (start with all sources in the queue).
- Edges arriving one by one, "are these now connected?": union-find.
Example
Shortest distance (in edges) from node 0 to every node, with BFS, on the graph in the first picture:
from collections import deque, defaultdict
def bfs_distances(n, edges, start):
adj = defaultdict(list)
for a, b in edges: # undirected: add both directions
adj[a].append(b)
adj[b].append(a)
dist = [-1] * n # -1 means not visited yet
dist[start] = 0
q = deque([start])
while q:
u = q.popleft()
for v in adj[u]:
if dist[v] == -1: # mark when you enqueue, not when you dequeue
dist[v] = dist[u] + 1
q.append(v)
return dist
int[] bfsDistances(int n, int[][] edges, int start) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
for (int[] e : edges) {
adj.get(e[0]).add(e[1]);
adj.get(e[1]).add(e[0]);
}
int[] dist = new int[n];
Arrays.fill(dist, -1);
dist[start] = 0;
Deque<Integer> q = new ArrayDeque<>();
q.offer(start);
while (!q.isEmpty()) {
int u = q.poll();
for (int v : adj.get(u)) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
q.offer(v);
}
}
}
return dist;
}
vector<int> bfsDistances(int n, const vector<pair<int, int>>& edges, int start) {
vector<vector<int>> adj(n);
for (auto [a, b] : edges) { adj[a].push_back(b); adj[b].push_back(a); }
vector<int> dist(n, -1);
dist[start] = 0;
queue<int> q;
q.push(start);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : adj[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
return dist;
}
func bfsDistances(n int, edges [][2]int, start int) []int {
adj := make([][]int, n)
for _, e := range edges {
adj[e[0]] = append(adj[e[0]], e[1])
adj[e[1]] = append(adj[e[1]], e[0])
}
dist := make([]int, n)
for i := range dist {
dist[i] = -1
}
dist[start] = 0
queue := []int{start}
for len(queue) > 0 {
u := queue[0]
queue = queue[1:]
for _, v := range adj[u] {
if dist[v] == -1 {
dist[v] = dist[u] + 1
queue = append(queue, v)
}
}
}
return dist
}
Time: O(V + E). Space: O(V + E) for the adjacency list, O(V) for the queue and distances. For edges [[0,1],[0,2],[1,3],[2,3],[3,4]] the result is [0, 1, 1, 2, 3].
Counting connected groups uses DFS instead: start a DFS from every node that hasn't been seen yet, and count how many times you start.
def count_components(n, edges):
adj = defaultdict(list)
for a, b in edges:
adj[a].append(b)
adj[b].append(a)
seen = [False] * n
def dfs(u):
seen[u] = True
for v in adj[u]:
if not seen[v]:
dfs(v)
count = 0
for u in range(n):
if not seen[u]:
count += 1
dfs(u)
return count
Common mistakes
- No visited set. Graphs have cycles; without one, BFS and DFS loop forever.
- Marking visited too late in BFS. Mark a node when you add it to the queue. Marking on removal lets the same node be queued many times.
- Adding only one direction for an undirected edge.
- Forgetting isolated nodes. Nodes with no edges never appear in the edge list; loop over
range(n), not just the keys of the adjacency map. - Using DFS for shortest paths. DFS finds a path, not the shortest. Use BFS (or Dijkstra with weights).
- Recursion depth. A DFS on a 1,000 × 1,000 grid can recurse a million levels deep; Python's default limit is 1,000. Use an explicit stack or BFS for big grids.
- Grid bounds. Check
0 <= r < rows and 0 <= c < colsbefore reading a neighbour.
Say this in the interview
- "This is a graph problem: the courses are nodes and each prerequisite is a directed edge."
- "I'll build an adjacency list, which is O(V + E) memory, and run BFS because every move costs one step, so the first time I reach the target is the shortest path."
- "I'll mark nodes visited when I enqueue them so nothing is processed twice. Total time is O(V + E)."
Used in
- Patterns: Graph BFS and DFS, Topological Sort, Union-Find
- Problems: Number of Islands, Clone Graph, Rotting Oranges, Course Schedule, Network Delay Time, Word Ladder
- Data structures: Stacks and Queues, Binary Trees (a tree is a graph without cycles), Heaps (Dijkstra)