Graphs: representation & traversal
A tree is a graph with no cycles and one root — now drop both restrictions.
A graph is nodes plus connections, nothing more
Trees have exactly one root and no cycles. A graph relaxes both: any node can connect to any other node, connections can be one-way (directed) or two-way (undirected), and cycles are allowed. That generality is why graphs model almost anything — social networks, road maps, dependency chains, web pages linking to each other.
Two ways to store one, and when each wins
| Adjacency list | Adjacency matrix | |
|---|---|---|
| Space | O(V + E) | O(V²) — wasteful for sparse graphs |
| "Are X, Y connected?" | O(degree of X) | O(1) |
| "Give me all of X's neighbors" | O(degree of X) — direct | O(V) — scan the whole row |
| Best for | most real interview graphs (sparse) | dense graphs, or when O(1) edge lookup matters most |
// building an adjacency list from an edge list — the shape you'll write constantly
function buildGraph(n, edges) {
const graph = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
graph[u].push(v);
graph[v].push(u); // omit this line for a DIRECTED graph
}
return graph;
}DFS — go deep, backtrack when stuck
// recursive DFS — the call stack IS the "backtrack" mechanism, for free
function dfs(graph, start, visited = new Set()) {
visited.add(start);
console.log(start);
for (const neighbor of graph[start]) {
if (!visited.has(neighbor)) dfs(graph, neighbor, visited);
}
return visited;
}
// iterative DFS — same order, explicit stack instead of recursion
function dfsIterative(graph, start) {
const visited = new Set([start]);
const stack = [start];
while (stack.length) {
const node = stack.pop();
for (const neighbor of graph[node]) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
stack.push(neighbor);
}
}
}
return visited;
}BFS — spread outward, layer by layer
function bfs(graph, start) {
const visited = new Set([start]);
const queue = [start];
const order = [];
while (queue.length) {
const node = queue.shift();
order.push(node);
for (const neighbor of graph[node]) {
if (!visited.has(neighbor)) {
visited.add(neighbor); // mark visited when ENQUEUED, not when dequeued
queue.push(neighbor);
}
}
}
return order;
}
⚠ Mark visited on enqueue, not on dequeue
If you wait to mark a node visited until you dequeue it, the same node
can be pushed onto the queue multiple times by different neighbors
before it's ever processed — wasted work, and on a graph with cycles it
can blow up badly. Mark it the instant it's added to the queue.
DFS vs BFS — the complexity is identical, the use case isn't
| DFS | BFS | |
|---|---|---|
| Time | O(V + E) | O(V + E) |
| Space | O(V) — recursion stack or explicit stack | O(V) — the queue, can hold a whole "ring" |
| Finds shortest path (unweighted)? | no | yes — guaranteed |
| Natural for | "does a path exist," cycle detection, backtracking-style exploration | shortest path, "closest," level-by-level problems |
Say it like this → "Both visit every node and
edge once, so they're both O(V + E) — the choice isn't about speed, it's
about the guarantee I need. BFS explores in strict distance order, so
it's the only one of the two that guarantees the first time I reach a
node is via a shortest path."
Recognizing it in an unseen problem
- Input described as nodes/edges, a grid (adjacent cells = edges), or "connections between X and Y"
- "Shortest path," "fewest steps," "minimum number of moves" on an unweighted graph → BFS
- "Does a path exist," "all paths," "explore every option" → DFS
- A 2D grid where you move up/down/left/right is a graph in disguise — each cell is a node, each valid move is an edge
Practice this layer
Opens in the editor — write it, run it, and check it against real tests.