Overview
A graph is a set of vertices connected by edges. Roads between cities, friendships, web links, course prerequisites and the cells of a maze are all graphs. Trees are a special case — connected and without cycles — so everything you learned about tree traversal carries over, with one addition: because graphs can contain cycles, you must remember which vertices you have already visited.
Breadth-first search (BFS) explores in rings of increasing distance using a queue, so in an unweighted graph it finds shortest paths. Depth-first search (DFS) dives as deep as possible before backtracking, using recursion or a stack, and is the natural fit for connectivity, cycle detection and exploring every path. Both visit each vertex and edge once: O(V + E).
Key concepts
Tick a concept once you can explain it in your own words without notes.
Complexity cheat sheet
| Operation | Cost |
|---|---|
| BFS / DFS (adjacency list) | O(V + E) time, O(V) space |
| BFS / DFS (adjacency matrix) | O(V²) |
| Grid traversal | O(rows × cols) |
Patterns to recognise
Flood fill / count components
Use it for: Number of islands, max area of island, provinces.
Loop over all vertices; start a traversal from each unvisited one and count.
Multi-source BFS
Use it for: Rotting oranges, walls and gates, distance to nearest 0.
Put every source in the queue at distance 0, then run one BFS.
Two-colouring
Use it for: Is graph bipartite, possible bipartition.
Colour neighbours opposite colours during BFS/DFS; a conflict means not bipartite.
Code template
from collections import deque
def num_islands(grid):
rows, cols = len(grid), len(grid[0])
islands = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] != '1':
continue
islands += 1
grid[r][c] = '0' # mark when enqueuing
queue = deque([(r, c)])
while queue:
y, x = queue.popleft()
for dy, dx in ((1, 0), (-1, 0), (0, 1), (0, -1)):
ny, nx = y + dy, x + dx
if 0 <= ny < rows and 0 <= nx < cols and grid[ny][nx] == '1':
grid[ny][nx] = '0'
queue.append((ny, nx))
return islands
int numIslands(vector<vector<char>>& grid) {
int rows = grid.size(), cols = grid[0].size(), islands = 0;
const int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
for (int r = 0; r < rows; ++r)
for (int c = 0; c < cols; ++c) {
if (grid[r][c] != '1') continue;
++islands;
grid[r][c] = '0'; // mark when enqueuing
queue<pair<int, int>> q;
q.push({r, c});
while (!q.empty()) {
auto [y, x] = q.front(); q.pop();
for (auto& d : dirs) {
int ny = y + d[0], nx = x + d[1];
if (ny >= 0 && ny < rows && nx >= 0 && nx < cols && grid[ny][nx] == '1') {
grid[ny][nx] = '0';
q.push({ny, nx});
}
}
}
}
return islands;
}
Common mistakes
- Marking visited when dequeuing instead of enqueuing lets the same cell enter the queue many times.
- For undirected graphs, add each edge in both directions.
- Graphs can be disconnected — loop over every vertex, not just vertex 0.
- Recursive DFS on a 1000 × 1000 grid will overflow the stack in many languages; prefer BFS or an explicit stack.
Quick check
Three questions on BFS & DFS. Get all three right to earn +15 XP.
-
An adjacency list for a graph with V vertices and E edges uses:
One list per vertex, one entry per edge end.
-
In an unweighted graph, which algorithm finds the shortest path by number of edges?
BFS reaches vertices in order of distance from the source.
-
What goes wrong if a graph traversal has no visited set?
Marking vertices when they are first reached keeps the traversal O(V + E).
Challenges
Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.
- Flood FillLeetCode Easy +20
- Find if Path Exists in GraphLeetCode Easy +20
- Number of IslandsLeetCode Medium +40
- Max Area of IslandLeetCode Medium +40
- Clone GraphLeetCode Medium +40
- Rotting OrangesLeetCode Medium +40
- Pacific Atlantic Water FlowLeetCode Medium +40
- Is Graph Bipartite?LeetCode Medium +40
- Word LadderLeetCode Hard +70
Stuck on BFS & DFS?Ask Orbi for a hint, a fresh explanation or a review of your code.
Ask the tutor