Graph Traversal (BFS, DFS, Topological Sort)
Representing graphs, BFS for shortest unweighted paths, DFS for components and cycles, grids as graphs, multi-source BFS, bipartite checks and topological ordering.
Graph vocabulary
A graph is a set of vertices (nodes) connected by edges.
- Directed (one-way edges, e.g. prerequisites) vs undirected (two-way, e.g. friendships).
- Weighted (edges have costs) vs unweighted.
- Cyclic vs acyclic. A directed acyclic graph is a DAG.
- Connected component: a maximal set of mutually reachable nodes.
- Degree: number of edges at a node (in-degree/out-degree for directed).
- A tree is a connected, acyclic, undirected graph with exactly n − 1 edges.
Representations
from collections import defaultdict
# adjacency list from an edge list — the default choice
adj = defaultdict(list)
for u, v in edges:
adj[u].append(v)
adj[v].append(u) # omit for directed graphs
# weighted
wadj = defaultdict(list)
for u, v, w in weighted_edges:
wadj[u].append((v, w))
vector<vector<int>> adj(n);
for (auto& e : edges) {
adj[e[0]].push_back(e[1]);
adj[e[1]].push_back(e[0]); // omit for directed
}
vector<vector<pair<int,int>>> wadj(n); // (neighbor, weight)
| Representation | Space | Check edge (u,v) | Iterate neighbours |
|---|---|---|---|
| Adjacency list | O(V + E) | O(deg) | O(deg) |
| Adjacency matrix | O(V²) | O(1) | O(V) |
| Edge list | O(E) | O(E) | O(E) |
Use a list almost always; a matrix for dense graphs or Floyd-Warshall; an edge list for Kruskal / Bellman-Ford.
BFS: breadth-first search
Explores in layers by distance from the source using a queue. In an unweighted graph, the first time BFS reaches a node is along a shortest path.
from collections import deque
def bfs(start, adj, n):
dist = [-1] * n
dist[start] = 0
q = deque([start])
while q:
u = q.popleft()
for v in adj[u]:
if dist[v] == -1: # mark when ENQUEUED, not when popped
dist[v] = dist[u] + 1
q.append(v)
return dist
vector<int> bfs(int start, const vector<vector<int>>& adj) {
vector<int> dist(adj.size(), -1);
queue<int> q;
dist[start] = 0; 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;
}
Watch BFS vs DFS vs Dijkstra vs A* explore a grid in the pathfinding visualizer.
BFS on a grid
from collections import deque
def shortest_path_grid(grid, start, target):
R, C = len(grid), len(grid[0])
q = deque([(start[0], start[1], 0)])
seen = {start}
while q:
r, c, d = q.popleft()
if (r, c) == target:
return d
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == 0 and (nr, nc) not in seen:
seen.add((nr, nc))
q.append((nr, nc, d + 1))
return -1
Multi-source BFS
Push all sources at distance 0. The BFS computes, for every node, the distance to the nearest source — in one pass.
def oranges_rotting(grid):
R, C = len(grid), len(grid[0])
q, fresh = deque(), 0
for r in range(R):
for c in range(C):
if grid[r][c] == 2:
q.append((r, c))
elif grid[r][c] == 1:
fresh += 1
minutes = 0
while q and fresh:
for _ in range(len(q)): # one minute = one layer
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 < R and 0 <= nc < C and grid[nr][nc] == 1:
grid[nr][nc] = 2
fresh -= 1
q.append((nr, nc))
minutes += 1
return -1 if fresh else minutes
BFS over states
When the “graph” is a state space, the node is a tuple of everything that matters: (position, keys_collected), (node, visited_mask), a lock combination string. Same algorithm, bigger seen set.
0-1 BFS
If edge weights are only 0 or 1, use a deque: push weight-0 neighbours to the front and weight-1 neighbours to the back. O(V + E), no heap needed.
DFS: depth-first search
Goes as deep as possible before backtracking. Great for reachability, connected components, cycle detection, topological order, and anything path-based.
def count_components(n, adj):
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]:
dfs(u)
count += 1
return count
int countComponents(int n, vector<vector<int>>& adj) {
vector<bool> seen(n, false);
function<void(int)> dfs = [&](int u) {
seen[u] = true;
for (int v : adj[u]) if (!seen[v]) dfs(v);
};
int count = 0;
for (int u = 0; u < n; u++) if (!seen[u]) { dfs(u); count++; }
return count;
}
Grid DFS (flood fill / islands)
def num_islands(grid):
R, C = len(grid), len(grid[0])
def sink(r, c):
if r < 0 or r >= R or c < 0 or c >= C or grid[r][c] != "1":
return
grid[r][c] = "0" # mark visited by mutating the grid
sink(r + 1, c); sink(r - 1, c); sink(r, c + 1); sink(r, c - 1)
count = 0
for r in range(R):
for c in range(C):
if grid[r][c] == "1":
sink(r, c)
count += 1
return count
def sink_iterative(grid, r, c):
stack = [(r, c)]
grid[r][c] = "0"
while stack:
r, c = stack.pop()
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]) and grid[nr][nc] == "1":
grid[nr][nc] = "0"
stack.append((nr, nc))
Reverse thinking: start from the boundary
“Which cells can reach the ocean / border?” is easier as “which cells can the ocean reach going uphill?” — DFS from the border inward (Pacific Atlantic, Surrounded Regions, Number of Enclaves).
Cycle detection
Undirected graph: during DFS, reaching an already-visited node that isn't your parent means a cycle. (Or use Union-Find: an edge joining two nodes already in the same set closes a cycle.)
Directed graph: use three colors — white (unvisited), gray (on the current DFS path), black (finished). An edge to a gray node is a back edge → cycle.
def has_cycle_directed(n, adj):
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * n
def dfs(u):
color[u] = GRAY
for v in adj[u]:
if color[v] == GRAY:
return True
if color[v] == WHITE and dfs(v):
return True
color[u] = BLACK
return False
return any(color[u] == WHITE and dfs(u) for u in range(n))
Bipartite check (2-coloring)
A graph is bipartite iff it has no odd cycle iff you can 2-color it so every edge joins different colors.
def is_bipartite(graph):
color = [-1] * len(graph)
for s in range(len(graph)): # graph may be disconnected
if color[s] != -1:
continue
color[s] = 0
q = deque([s])
while q:
u = q.popleft()
for v in graph[u]:
if color[v] == -1:
color[v] = 1 - color[u]
q.append(v)
elif color[v] == color[u]:
return False
return True
Topological sort
A linear order of a DAG's nodes such that every edge u → v has u before v. Exists iff the graph has no directed cycle.
Kahn's algorithm (BFS on in-degrees)
from collections import deque
def topo_sort(n, edges): # edges: (u, v) means u before v
adj = [[] for _ in range(n)]
indeg = [0] * n
for u, v in edges:
adj[u].append(v)
indeg[v] += 1
q = deque(u for u in range(n) if indeg[u] == 0)
order = []
while q:
u = q.popleft()
order.append(u)
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
return order if len(order) == n else [] # [] → cycle
vector<int> topoSort(int n, vector<vector<int>>& edges) {
vector<vector<int>> adj(n);
vector<int> indeg(n, 0), order;
for (auto& e : edges) { adj[e[0]].push_back(e[1]); indeg[e[1]]++; }
queue<int> q;
for (int u = 0; u < n; u++) if (!indeg[u]) q.push(u);
while (!q.empty()) {
int u = q.front(); q.pop();
order.push_back(u);
for (int v : adj[u]) if (--indeg[v] == 0) q.push(v);
}
if ((int)order.size() < n) return {}; // cycle
return order;
}
Useful extras:
- Processing level by level gives the minimum number of semesters (Parallel Courses).
- Using a min-heap instead of a queue gives the lexicographically smallest order.
- DP along the order computes longest paths / counts of paths in a DAG.
DFS-based topological sort
Post-order DFS, then reverse: a node is appended only after everything reachable from it.
def topo_dfs(n, adj):
seen, order = [False] * n, []
def dfs(u):
seen[u] = True
for v in adj[u]:
if not seen[v]:
dfs(v)
order.append(u)
for u in range(n):
if not seen[u]:
dfs(u)
return order[::-1] # (combine with 3-color to detect cycles)
BFS or DFS?
| Need | Use |
|---|---|
| shortest path, unweighted | BFS |
| minimum number of steps/moves/transformations | BFS |
| distance to the nearest of many sources | multi-source BFS |
| explore/count components, flood fill | either (DFS is shorter to write) |
| detect cycles, topological order, path enumeration | DFS (or Kahn for topo) |
| weighted shortest path | Dijkstra → Shortest Paths |
| dynamic connectivity (edges added over time) | Union-Find → Union-Find |
Complexity
BFS and DFS both run in O(V + E) time and O(V) space. On an R × C grid, that's O(R·C).
Common mistakes
- Marking visited on pop instead of push in BFS.
- Forgetting disconnected components (loop over all nodes as starts).
- Adding only one direction for undirected edges.
- Mutating the input grid when the caller needs it intact (copy it or use a
seenset). - Recursion depth on large grids in Python.
- Checking bounds after indexing into the grid.
Practice problems
Ordered roughly from warm-up to hard. Try each one for 25–40 minutes before peeking at the key idea; if you needed the hint, mark it “review” and redo it in a few days.
Click the box to cycle: solved ✓ → needs review ↺ → not started. Links open LeetCode.