Graphs: Representations, BFS and DFS
Model networks as vertices and edges, choose between adjacency lists and matrices, and explore with breadth-first and depth-first search.
intermediate50 min#graphs#bfs#dfs#adjacency-list#traversal
Prerequisites: Trees and Binary Search Trees, Stacks and Queues, Hash Tables
Why it matters
Graphs describe relationships: roads between cities, friends in a social network, links between web pages, dependencies between packages, states in a game. A huge share of real problems become easy once you notice they are graph problems in disguise, and a tree is simply a graph with no cycles. Two traversals, BFS and DFS, are the foundation for nearly every graph algorithm that follows.
Intuition
A graph is a set of vertices (nodes) joined by edges. Edges can be undirected (friendship) or directed (follows), and may carry a weight (distance, cost). A path is a sequence of edges, a cycle is a path that returns to its start, and a graph is connected if every vertex can reach every other.
Exploring a maze gives the two traversals. DFS is the strategy of one person with a ball of string: go as deep as possible down one corridor, and back up only at a dead end. BFS is a crowd spreading out: everyone takes one step, then everyone takes one more, so you reach all places one step away before any place two steps away. That layering is why BFS finds the shortest path when all edges count equally.
A --- B
| |
C --- D --- E
BFS from A: A | B C | D | E (layers 0, 1, 1, 2, 3)
DFS from A: A B D C E (dives before backing up)
How it works
Representations. Let V be the number of vertices and E the number of edges.
- Adjacency list: for each vertex, a list of its neighbors. Space is O(V + E). Iterating the neighbors of a vertex is proportional to its degree. This is the default, because most real graphs are sparse (E is far smaller than V squared).
- Adjacency matrix: a V by V grid where cell
[u][v]is 1 (or the weight) if the edge exists. Space is O(V squared). Checking whether an edge exists is O(1), but listing neighbors costs O(V). Use it for small or dense graphs. - Edge list: just a list of pairs. Simple for sorting edges (Kruskal's algorithm) but slow for neighbor queries.
For an undirected graph, store each edge in both directions. For a directed graph, store it once.
Here is the five-vertex graph from the code in both forms.
The visited set. Unlike a tree, a graph can contain cycles, so a traversal must remember what it has seen or it will loop forever. Mark a vertex as seen when you enqueue or push it, not when you pop it, otherwise the same vertex can be queued many times.
BFS uses a queue. Pop a vertex, push each unseen neighbor and record its distance as one more than the current vertex. Each vertex and edge is processed once: O(V + E). The recorded distances are shortest-path lengths in an unweighted graph.
BFS from A. Green is the vertex just popped, amber vertices are waiting in the queue, and highlighted edges show how each vertex was first discovered. The layers are the distances: 0, then B and C at 1, D at 2, E at 3.
DFS uses a stack, either explicitly or through recursion. Visit a vertex, then recurse into each unseen neighbor. Also O(V + E). DFS is the tool for reachability, finding connected components, detecting cycles, and topological sorting.
DFS from A. Green is the current vertex, amber vertices are on the recursion stack (still waiting to try their other neighbors), highlighted edges are the ones followed. DFS goes as deep as it can before backing up.
| Operation | Time | Notes |
|---|---|---|
| BFS / DFS (adjacency list) | O(V + E) | Each vertex and edge once |
| BFS / DFS (adjacency matrix) | O(V squared) | Row scan per vertex |
| Edge exists? (list / matrix) | O(degree) / O(1) | Matrix wins for lookups |
| List neighbors (list / matrix) | O(degree) / O(V) | List wins for sparse graphs |
| Space (list / matrix) | O(V + E) / O(V squared) | Matrix wasteful when sparse |
Code: BFS, DFS and reachability
import json
from collections import deque
def show(*xs):
print(*(json.dumps(x, separators=(',', ':')) for x in xs))
edges = [("A", "B"), ("A", "C"), ("B", "D"), ("C", "D"), ("D", "E")]
graph = {}
for u, v in edges: # undirected: store both directions
graph.setdefault(u, []).append(v)
graph.setdefault(v, []).append(u)
def bfs(graph, start):
"""Visit order and shortest distance (in edges) from start."""
dist = {start: 0}
order = []
q = deque([start])
while q:
u = q.popleft()
order.append(u)
for v in graph[u]:
if v not in dist:
dist[v] = dist[u] + 1
q.append(v)
return order, dist
def dfs(graph, u, seen=None):
seen = set() if seen is None else seen
seen.add(u)
order = [u]
for v in graph[u]:
if v not in seen:
order += dfs(graph, v, seen)
return order
def has_path(graph, src, dst):
seen, stack = {src}, [src]
while stack:
u = stack.pop()
if u == dst:
return True
for v in graph.get(u, []):
if v not in seen:
seen.add(v)
stack.append(v)
return False
show(bfs(graph, "A")[0])
show(bfs(graph, "A")[1])
show(dfs(graph, "A"))
graph["X"] = ["Y"]
graph["Y"] = ["X"]
show(has_path(graph, "A", "E"), has_path(graph, "A", "Y"))
# adjacency matrix for the first five nodes
names = ["A", "B", "C", "D", "E"]
idx = {n: i for i, n in enumerate(names)}
m = [[0] * 5 for _ in range(5)]
for u, v in edges:
m[idx[u]][idx[v]] = m[idx[v]][idx[u]] = 1
show(m[idx["D"]])const show = (...xs) => console.log(xs.map((x) => JSON.stringify(x)).join(" "));
const edges = [["A", "B"], ["A", "C"], ["B", "D"], ["C", "D"], ["D", "E"]];
const graph = new Map();
const addEdge = (u, v) => {
if (!graph.has(u)) graph.set(u, []);
graph.get(u).push(v);
};
for (const [u, v] of edges) {
addEdge(u, v); // undirected: store both directions
addEdge(v, u);
}
// Visit order and shortest distance (in edges) from start.
function bfs(graph, start) {
const dist = new Map([[start, 0]]);
const order = [];
const queue = [start];
for (let head = 0; head < queue.length; head++) {
const u = queue[head];
order.push(u);
for (const v of graph.get(u)) {
if (!dist.has(v)) {
dist.set(v, dist.get(u) + 1);
queue.push(v);
}
}
}
return [order, Object.fromEntries(dist)];
}
function dfs(graph, u, seen = new Set()) {
seen.add(u);
const order = [u];
for (const v of graph.get(u)) {
if (!seen.has(v)) order.push(...dfs(graph, v, seen));
}
return order;
}
function hasPath(graph, src, dst) {
const seen = new Set([src]);
const stack = [src];
while (stack.length) {
const u = stack.pop();
if (u === dst) return true;
for (const v of graph.get(u) ?? []) {
if (!seen.has(v)) {
seen.add(v);
stack.push(v);
}
}
}
return false;
}
const [order, dist] = bfs(graph, "A");
show(order);
show(dist);
show(dfs(graph, "A"));
graph.set("X", ["Y"]);
graph.set("Y", ["X"]);
show(hasPath(graph, "A", "E"), hasPath(graph, "A", "Y"));
// adjacency matrix for the first five nodes
const names = ["A", "B", "C", "D", "E"];
const idx = Object.fromEntries(names.map((n, i) => [n, i]));
const m = names.map(() => new Array(5).fill(0));
for (const [u, v] of edges) m[idx[u]][idx[v]] = m[idx[v]][idx[u]] = 1;
show(m[idx["D"]]);Both versions print:
["A","B","C","D","E"]
{"A":0,"B":1,"C":1,"D":2,"E":3}
["A","B","D","C","E"]
true false
[0,1,1,0,1]
BFS visits A, then its neighbors B and C, then D, then E, and reports their distances. DFS dives A, B, D, then backs up to C before E. The vertices X and Y form a separate component, so there is no path from A to Y. The last line is row D of the adjacency matrix: D is connected to B, C and E.
Common pitfalls
- No visited set: any graph with a cycle (including every undirected edge, which is a two-step cycle) will loop forever.
- Marking visited too late: marking on pop lets a vertex enter the queue repeatedly, which can blow up the running time.
- Using
list.pop(0)orshift()as the queue: each call is O(n). Usecollections.dequein Python, and a head index (as above) in JavaScript. - Forgetting disconnected graphs: one traversal from one start only reaches one component. Loop over all vertices to cover everything.
- Recursion limits: DFS on a path of 100,000 vertices overflows the default stack in Python and JavaScript. Convert to an explicit stack.
- Undirected edge stored once: the neighbor lookup then fails in one direction.
Practice
Does a path exist? easy
Hint
Any traversal from the source works. What do you check when you pop a vertex?
Show solution
Run BFS or DFS from the source with a visited set and return true as soon as you reach the destination, false if the traversal ends first. O(V + E).
Number of islands medium
Hint
Treat each land cell as a vertex and loop over every cell as a possible start.
Show solution
Scan the grid. When you find an unvisited land cell, increment the count and flood-fill (DFS or BFS) over its land neighbors, marking them visited. Each cell is processed once, O(rows times columns).
Shortest path in a binary maze medium
Hint
Which traversal discovers vertices in order of distance?
Show solution
BFS from the start cell, storing the distance with each queued cell and stopping at the goal. Because every step has the same cost, the first time BFS reaches a cell is via a shortest path. DFS cannot promise that.
Clone a graph hard
Hint
You need a map from each original node to its copy, which doubles as the visited set.
Show solution
Traverse with BFS or DFS. When you meet an original node, create its copy if it is not yet in the map. For each neighbor, ensure a copy exists and append it to the copy's neighbor list. The map prevents infinite loops on cycles. O(V + E).
Interview questions
- Adjacency list or matrix? The list for sparse graphs (the common case): O(V + E) space. The matrix for dense graphs or when you need O(1) edge lookup.
- When is BFS better than DFS? For shortest paths in unweighted graphs and level-by-level processing. DFS suits exhaustive exploration, cycles, components and topological order.
- What is the complexity of BFS? O(V + E) with an adjacency list.
- How do you handle a graph with cycles? Keep a visited set, marked when a vertex is first discovered.
- How is a tree different from a graph? A tree is a connected graph with no cycles and exactly V minus 1 edges.
Interviewers look for: asking whether the graph is directed, weighted, or possibly disconnected, choosing a representation with a reason, and marking visited at the right moment.
Quick check
You need the fewest number of edges between two people in a social network where every connection counts the same. Which approach fits?
Finished this lesson?
Further resources
- Graph (abstract data type) (Wikipedia) (article)
- Breadth-first search (Wikipedia) (article)
- Depth-first search (Wikipedia) (article)