A graph is a set of nodes (also called vertices) connected by edges. Road maps, social networks, course prerequisites, and even a grid of cells are all graphs. Most graph interview questions come down to one of a few searches, so the work is usually in spotting the graph and choosing the search.
Words you'll need
- Directed edges go one way (A follows B); undirected edges go both ways (A and B are friends).
- Weighted edges have a cost (minutes, distance); unweighted edges all cost the same.
- A cycle is a path that returns to where it started.
- A connected component is a group of nodes that can all reach each other.
Six nodes and seven edges. Every node can reach every other, so it's one connected component.
Representing a graph
| Representation | Space | Good for |
|---|---|---|
| Adjacency list: a map from each node to its neighbours | O(V + E) | Almost every interview problem |
| Adjacency matrix: a V × V table of true/false | O(V²) | Dense graphs, "is there an edge?" in O(1) |
| Edge list: a list of pairs | O(E) | Input format; usually convert it to an adjacency list first |
1from collections import defaultdict2graph = defaultdict(list)node -> list of its neighbours
3for a, b in edges:4 graph[a].append(b)an edge from a to b...
5 graph[b].append(a) # leave this out for a directed graph...and back, if it's undirected
The two searches
Depth-first search (DFS) follows one path as far as it goes, then backs up. Write it with recursion or a stack. Use it to explore everything reachable, count components, and detect cycles.
Breadth-first search (BFS) visits all nodes one step away, then two steps, and so on, using a queue. In an unweighted graph, BFS finds the shortest path (fewest edges).
Start at A: distance 0.
Both are O(V + E): every node and edge is handled once, as long as you mark nodes as visited. Without a visited set, a graph with a cycle sends you round forever.
Watch out
Forget the visited set and a single cycle sends your search round and round forever.
Grids are graphs
A grid of cells is a graph where each cell's neighbours are the cells up, down, left and right. You don't need to build an adjacency list: compute the neighbours on the fly, and check they're inside the grid.
Up, down, left and right: (r−1, c), (r+1, c), (r, c−1), (r, c+1).
Ordering with prerequisites
If edges mean "must come before", a valid order exists only if there's no cycle. Two ways to find one (a topological order):
- Kahn's algorithm (BFS): repeatedly take a node with no remaining prerequisites.
- DFS with three colours: unvisited, in progress, done. Reaching an "in progress" node again means you've found a cycle.
Shortest paths with weights
When edges have different non-negative costs, BFS isn't enough. Dijkstra's algorithm always expands the closest unfinished node next, using a min-heap (heapq in Python). It runs in O(E log V).
Common mistakes
- Forgetting the visited set, or marking a node visited too late (mark it when you add it to the queue, not when you take it out, in BFS).
- Treating a directed graph as undirected, or the other way round.
- Recursion depth: a DFS over a long chain of 100,000 nodes can overflow Python's call stack. Use an explicit stack.
Nice work!
You've got the big idea. Try the quick quiz below, then put it to work on the practice problems.