Graphs: Representation, BFS and DFS

Graphs and Algorithmic Techniques · 40 min

Data structures & algorithms

Graphs: representation, BFS and DFS

A graph is a list of who is next to whom. Build one from an edge list, then run BFS and DFS from node 0 on the same six-node graph — same ten lines, one container swapped, two different visit orders.

Swap the queue for a stack yourself →
Keep a visited set and a frontier of nodes found but not yet explored. Take one out, then mark and add every unseen neighbour. Queue for the frontier gives BFS; stack gives DFS. Nothing else changes.

01 The idea

Nodes, edges, and a frontier of things to look at next

A graph is a set of things plus the connections between them. The things are nodes; the connections are edges. Cities and roads, users and friendships, board positions and legal moves — once you see the graph, the same two traversals point at all of them.

You already know a special case. A tree is a graph that is connected and has no cycles, so there is exactly one path between any two nodes. A general graph drops both restrictions, which is why graph traversal needs a visited set and walking a rooted tree does not: a tree’s child pointers only ever point down, while graph edges run both ways and a single edge would send you back and forth forever.

Node and edgeA node is one item; an edge joins two. Here node 0 and node 3 are joined, so 3 is a neighbour of 0 and 0 is a neighbour of 3.
Adjacency listAn array where slot i holds i’s neighbours. adj[0] = [1, 3, 5]. This is the representation you write in an interview.
FrontierNodes discovered but not yet taken out and explored. A queue for BFS, a stack for DFS — that one choice is the whole difference.

02 Hand trace

From an edge list to a BFS order

Seven edges, written the way input actually arrives: 0-1 1-2 2-3 3-4 4-5 5-0 0-3. Six nodes in a ring, one chord across from 0 to 3. It is undirected, so every edge goes into the list twice, once at each end.

THE GRAPH · 6 NODES, 7 EDGES the chord 0 1 2 3 4 5 ADJACENCY LIST · adj[i] = neighbours of i 0 → 1, 3, 5 1 → 0, 2 2 → 1, 3 3 → 0, 2, 4 4 → 3, 5 5 → 0, 4 Every edge appears twice — 7 edges, 14 entries

Node 0 is where every traversal in this lesson starts. The dashed chord is the only edge that is not part of the ring, and it is what stops the graph being a simple cycle.

WHY THE LIST IS THE DEFAULT Adjacency list 14 numbers stored Adjacency matrix 36 cells, 22 of them zero On 6 nodes the gap is small. On a million users with 30 friends each it is 60M vs 10¹². THE 6 × 6 MATRIX 0 1 2 3 4 5 0 1 1 1 1 1 1 2 1 1 3 1 1 1 4 1 1 5 1 1 Each blue cell is one direction of one edge, so the grid is symmetric about its diagonal — that symmetry is what undirected looks like. The empty cells are the cost. They are stored, and scanned, for edges that do not exist.

The list stores two numbers per edge. The matrix stores a cell for every possible edge, whether or not it is there — which is why listing one node’s neighbours costs O(V) on a matrix and O(deg u) on a list.

Now run BFS from node 0. Each row is one node coming out of the queue. The boxes are the queue contents after that node was taken and its neighbours added; the rose box is the front, the node that comes out next. A dot means empty.

take 01350 visited · 1, 3 and 5 are all new, so all three join
take 13521 visited · 0 already seen, 2 is new and joins the back
take 35243 visited · 0 and 2 already seen, 4 is new
take 524·5 visited · 0 and 4 already seen, nothing joins
take 24··2 visited · both its neighbours already seen
take 4···4 visited · queue empty, all six nodes reached
visit order013524distance from 0, same order: 0 · 1 1 1 · 2 2

Read the queue column, not the order column. Node 0 puts all three neighbours in at once, so 1, 3 and 5 all come out before anything two edges away is even discovered. Redraw the graph by distance and that becomes the whole picture.

THE SAME SEVEN EDGES, DRAWN BY DISTANCE FROM 0 distance 0 distance 1 distance 2 0 1 3 5 2 4 edge BFS discovered a node on edge to an already-seen node

The five solid edges are the BFS tree; the two dashed ones lead somewhere already seen and discover nothing. BFS empties an entire level before the next one starts, which is exactly why the level a node appears on is its shortest distance.

03 Code

One loop, two containers

The trace you just followed is ten lines. Here it is twice. Apart from the name on line 1, the two blocks differ on line 3 and line 5, in one word each, and nowhere else.

BFS · frontier is a queue

function bfs(adj, start):    seen = {start}; order = []    frontier = Queue([start])     # container    while frontier is not empty:        node = frontier.takeFront()   # oldest out        order.append(node)        for nb in adj[node]:            if nb not in seen:                seen.add(nb); frontier.push(nb)    return order

DFS · frontier is a stack

function dfs(adj, start):    seen = {start}; order = []    frontier = Stack([start])     # container    while frontier is not empty:        node = frontier.takeTop()     # newest out        order.append(node)        for nb in adj[node]:            if nb not in seen:                seen.add(nb); frontier.push(nb)    return order
THE FRONTIER HOLDS 1, 3, 5 — WHICH COMES OUT? Queue takeFront() 1 3 5 OLDEST IN NEWEST IN hands back 1 — the graph fans out level by level Stack takeTop() 1 3 5 OLDEST IN NEWEST IN hands back 5 — the walk keeps going away from 0

Same three nodes, same order of arrival. The only question either container answers is which end you take from, and that single choice is the entire difference between the two traversals.

Only the container changes. On this graph that gives BFS 0 1 3 5 2 4 and DFS 0 5 4 3 2 1 — same graph, same start, same seven edges, same number of steps, different order.

BFS · QUEUE · 0 1 3 5 2 4 DFS · STACK · 0 5 4 3 2 1 0 1 1 2 2 5 3 3 4 6 5 4 0 1 1 6 2 5 3 4 4 3 5 2 the small filled badge is the position in the visit order

BFS takes 0’s three neighbours first and only then goes deeper. DFS walks right round the ring instead: adj[0] is [1, 3, 5], so the stack pushes 1, then 3, then 5 — and 5 is now on top.

Mark visited on line 9, when you push — not when you pop. Node 2 is a neighbour of both 1 and 3. Marking at push time means 3 finds it already seen and it enters the queue exactly once. Marking at pop time keeps the order and the O(V + E) time, but a node can be pushed once per neighbour that finds it, so the frontier grows to O(E) instead of O(V).

The stack version is not the recursion with the neighbours flipped. Marking at push time claims a node the moment anyone finds it, so the walk can be cut off from below. Start the console at node 3: the stack gives 3 4 5 2 1 0, which no recursive DFS can produce. Both are correct depth-first traversals; they are simply not the same order.

Recursive DFS is the same idea with the call stack doing the work. dfs(node): seen.add(node); order.append(node); for nb in adj[node]: if nb not in seen: dfs(nb). The frontier is now the pile of pending call frames, so graph depth is your memory bill and a chain of 100,000 nodes will overflow it.

Two things you get free from the same loop. Wrap it in an outer loop over every node and start a traversal only where the node is still unvisited: each start is one connected component. And a grid needs no adjacency list at all — the neighbours of (r, c) are the four cells around it. That is number-of-islands, and it is this loop unchanged.

05 Cheat sheet

The numbers you get asked for

What you ask of the graphAdjacency listAdjacency matrix
Memory for V nodes and E edgesO(V + E)O(V²)
Are u and v joined?O(deg u)O(1)
List u’s neighboursO(deg u)O(V)
One full BFS or DFSO(V + E)O(V²)
Add an edgeO(1)O(1)
This lesson’s graph, V = 6 and E = 714 numbers36 numbers
BFS gives shortest paths, DFS does notOn an unweighted graph the level at which BFS first reaches a node is the fewest edges to it. Write dist[nb] = dist[node] + 1 at push time and it costs nothing extra. Once edges carry weights, neither works — that is Dijkstra.
Both cost O(V + E) on a listEvery node enters the frontier once and every edge is looked at once from each end — here, 6 nodes taken and 14 edge checks, identical for both. Only the order differs.
The frontier is the memory billO(V) worst case either way. Do not confuse the explicit stack with recursion depth: on the star preset both peak at 5, on a chain both peak at 1. It is recursive DFS whose memory follows the longest path.

06 Where & why

Picking the container on purpose

BFS and DFS cost the same and reach the same nodes. They are still not interchangeable, because of what they hand you on the way. Pick by the information you need, not by which one you remember first.

Reach for BFS when…

You need the fewest edgesShortest path on an unweighted graph. The step at which BFS first reaches a node is the answer, and nothing found later can beat it.
The answer is probably closeMinimum moves on a board, word ladder, nearest exit. BFS finds a shallow answer without disappearing down a deep branch first.
You are flooding a gridNumber of islands, rotting oranges, flood fill. The four cells around (r, c) are its edges, so you never build a graph at all.
You must not blow the call stackA chain of 100,000 nodes overflows recursive DFS. BFS has no recursive form to overflow. For depth-first order that deep, write the explicit-stack version.

Use something else when…

SituationBetter choiceWhy
You need the order calls enter and leave — directed-cycle detection, or a topological order off finish timesRecursive DFSNeither the queue nor the push-marking stack produces entry and exit times; recursion gives them free.
You ask whether two nodes are connected over and over, with edges arriving as you goUnion-findNear-constant time per query with no traversal, merging components as edges arrive. For one question on a fixed graph, one traversal is simpler.
Edges carry different weightsDijkstraBFS counts edges, not cost, so it hands you a two-edge path that is dearer than a three-edge one.
The graph is dense — E close to V²An adjacency matrixThe list stops saving memory, and the matrix answers “are u and v joined?” in O(1).
You will not be asked to invent a traversal. You will be asked to recognise a graph inside a problem that never says the word — a grid, a set of dependencies, a list of pairs — and then to pick the container. Almost every graph question in an interview is this loop plus one small piece of bookkeeping.

07 Interview questions

Say these out loud

Question 7 is the one that separates people who have written BFS from people who have only read it.

What is a graph, and how is a tree different?
A graph is a set of nodes plus edges joining pairs of them. A tree is a graph that is connected and has no cycles, so exactly one path joins any two nodes. Drop those and you get cycles and multiple paths, which is why graph traversal needs a visited set. A rooted tree escapes without one because its child pointers go one way only.
Adjacency list or adjacency matrix — which do you use?
Adjacency list, almost always: O(V + E) memory against the matrix at O(V²), and real graphs are sparse — this lesson’s graph is 14 numbers as a list and 36 as a matrix. The matrix wins in two cases: the graph is dense with E close to V², or you keep asking “are u and v joined?”, which it answers in O(1).
How do you build an adjacency list from an edge list?
Create V empty lists first, then for every edge [a, b] append b to adj[a] and a to adj[b]. That second append is the only thing making it undirected. Creating all V lists up front matters because a node with no edges never appears in the edge list and would otherwise go missing.
What is the actual difference between BFS and DFS?
The container the frontier is kept in, and nothing else. A queue returns the oldest node you put in, so BFS fills the graph level by level. A stack returns the newest, so DFS walks away from the start and only comes back when it runs out of new ground. The same ten lines give 0 1 3 5 2 4 with a queue and 0 5 4 3 2 1 with a stack.
Time and space complexity of BFS and DFS?
Both are O(V + E) time on an adjacency list: every node enters the frontier once, and every edge is looked at once from each end. Both use O(V) extra space for the visited set plus the frontier. On an adjacency matrix both become O(V²), because listing one node’s neighbours means scanning a whole row of V entries.
Why does BFS give the shortest path on an unweighted graph, and DFS not?
BFS takes every node at distance d out of the queue before any node at distance d + 1, so the first time it reaches a node is by the fewest possible edges. Be precise if pushed: nodes at distance d + 1 are discovered earlier than that — what BFS never does is take one out early. Record dist[nb] = dist[node] + 1 at push time and the answer costs nothing extra. DFS commits to one branch first, so it can reach a node down a five-edge path that also sits one edge from the start.
Where exactly do you mark a node visited?
When you push it into the frontier, not when you take it out. Node 2 here is a neighbour of both 1 and 3; marking at push time means it enters the queue exactly once. Marking on the way out also works, as long as you skip a node that comes out already done — the visit order and the O(V + E) time both survive. What it costs is memory: a node can be pushed once for every neighbour that finds it, so the frontier grows to O(E) instead of O(V). Say that out loud, because the failure people expect here is a wrong answer and it is really a memory bug.
What happens if you drop the visited set entirely?
It never ends — and not only on a graph with a cycle. In an undirected adjacency list every single edge is itself a two-node loop: 0 pushes 1, 1 pushes 0 straight back, and the frontier grows forever. Load the acyclic “A tree” preset in the console above and exactly the same thing happens. Rooted tree traversal escapes only because child pointers go one way. A directed graph keeps terminating as long as it stays acyclic.
How do you count connected components?
Loop i from 0 to V − 1 and start a fresh traversal only when i is still unvisited. The number of times you start is the number of components. The traversal itself does not change at all — the outer loop is the whole new idea. A node with no edges is still a component of size one, and that is the case people forget.
Your iterative DFS gives a different order to your recursive DFS — is one wrong?
Neither is wrong, and reversing the neighbour list does not reliably make them agree. The easy half: a stack hands back the last thing pushed, so the iterative version works through adj[node] in reverse and reaches 5 first here where recursion reaches 1. The real half: marking at push time claims a node the moment anyone finds it, so the iterative walk can produce orders no recursion could — start at node 3 in the console and the stack gives 3 4 5 2 1 0. For entry and exit times, write the recursive version anyway.
Is “number of islands” really a graph problem?
Yes, and the graph is never built. Each land cell is a node and its edges are the up, down, left and right cells that are also land, so adj[node] becomes four offsets with a bounds check. The answer is then the component count: sweep the grid, start a traversal at every unvisited land cell, and count how many times you started. BFS and DFS both work.
When would you use neither BFS nor DFS?
When edges carry weights, use Dijkstra — BFS counts edges, so it will hand you a two-edge path that costs more than a three-edge one. When you are asked “are these two connected?” over and over while edges keep arriving, union-find answers each query in near-constant time with no traversal at all. And on a huge graph where you want one specific shortest path, bidirectional BFS or A* explores far less. BFS and DFS are the base case.

08 Practice problems

Build it, then traverse it

For each one, decide what the nodes are and what the edges are before you write a line, then name the container. Everything here is solvable with the ten lines from section 03 and a little bookkeeping.

Is there a path at all?

Easy
Given n nodes, an undirected edge list, a source s and a target t, return true if any path joins them and false otherwise. No distances, no order — just the answer.
Follow-up
The traversal does not have to finish: you can stop the instant t is marked. And s equal to t has to come back true even when s appears in no edge at all.
Show the hint
Either container gives the same answer here, so pick the one you can write without thinking. The only state you need is the marked set — ask what it would mean for t to be in it.

From matrix to list

Easy
You are handed the graph as an n × n adjacency matrix instead of an edge list. Return the equivalent adjacency list, each neighbour list in ascending order.
Follow-up
You have to read all n² cells whatever the answer turns out to be, so the conversion costs O(n²) even on a graph with three edges. And if the matrix is not symmetric it was never an undirected graph.
Show the hint
Work one row at a time and ask what m[i][j] = 1 tells you about slot i, about slot j, and what the case i = j should do.

The graph is not numbered

Medium
You are given a list of people, a list of friendship pairs — both by name — and one person. Return everyone reachable from that person in BFS order, as names.
Follow-up
Nothing hands you node numbers, so you have to invent them before a single adjacency list can exist, and the mapping has to work in both directions. Two people can also be listed as friends twice, once each way round.
Show the hint
Do the numbering as a separate first pass and keep both directions of it. After that, section 03 runs unchanged on integers and the last thing you do is translate back.

The largest component

Medium
Given n nodes and an undirected edge list, return the number of nodes in the largest connected component.
Follow-up
The marked set has to survive from one start to the next and the size counter must not. Mix those two lifetimes up and every graph reports a single component of size n — which looks correct on any connected example, so it passes the sample and fails everything else.
Show the hint
The outer sweep is the same one that counts components. The only new thing is a number each traversal has to hand back to the sweep that started it.

Two-colour the graph

Medium
Return true if every node can be coloured red or blue so that no edge joins two nodes of the same colour, using BFS.
Follow-up
Starting at node 0 only ever tests node 0’s component. Load the console’s “Two components” preset — a triangle 0-1-2 beside a separate path 3-4-5 — and start at 3: the half you can see is perfectly two-colourable and the graph is not.
Show the hint
The colour array can replace the marked set outright, because “no colour yet” and “not seen yet” are the same state. All the new work happens in the branch where section 03 simply skips a neighbour.

Return the path, not its length

Hard
Given an unweighted graph, a source and a destination, return the actual sequence of nodes along a shortest path, or an empty list if there is none.
Follow-up
You cannot read the path back out of the visit order. BFS here gives 0 1 3 5 2 4, so the node before 4 in the order is 2 — but 4 was discovered from 3, and 2 is not even a neighbour of 4.
Show the hint
The one instant you still know where a node came from is the instant you push it, so whatever you record has to be written on line 9, one number per node. Then work out which end of the answer you are building from.