Graphs: Representation, BFS and DFS

Graphs and Algorithmic Techniques · 40 min

Data structures & algorithms · Module 29

Graphs: representation, BFS and DFS

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

Swap the queue for a stack yourself →
6 nodes · 7 edges · nothing visited
→
BFS from 0 · 0 1 3 5 2 4

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, also called vertices. The connections are edges. Cities and roads, users and friendships, pages and links, board positions and legal moves — every one of these is a graph, and once you see the graph you can point the same two traversals at all of them.

You already know a special case. A tree is a graph with two restrictions: it is connected, and it has no cycles, so there is exactly one path between any two nodes. A general graph drops both. Two nodes can be joined by several paths, and a path can loop back to where it started. That is why graph traversal needs a visited set while walking a rooted tree does not: a tree's child pointers only ever point down, so you can never arrive back where you have been. Graph edges run both ways, and without a visited set even a single edge sends you back and forth forever.

Keep a visited set and a frontier of nodes you have found but not yet explored. Take one node out of the frontier, then mark and add every neighbour you have not seen. If the frontier is a queue you get BFS. If it is a stack you get DFS. Nothing else changes.
Node and edgeA node is one item in the graph; an edge joins two nodes. In this lesson's graph 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 the list of i's neighbours. adj[0] = [1, 3, 5] says node 0 touches 1, 3 and 5. This is the representation you write in an interview.
FrontierThe nodes you have discovered but not yet taken out and explored. It is a queue for BFS and a stack for DFS, and that one choice is the whole difference between them.

02 Hand trace

From an edge list to a BFS order

Here is the graph the whole lesson uses. Seven edges, written the way input actually arrives: 0-1 1-2 2-3 3-4 4-5 5-0 0-3. Six nodes 0 to 5 sit in a ring, and one extra edge cuts across from 0 to 3. It is undirected, so every edge goes into the list twice, once at each end. If you added it only once you would have built a directed graph, where an edge points one way and 3 being a neighbour of 0 says nothing about 0 being a neighbour of 3.

Nodeadj[node] — the listRow of the matrix
01, 3, 50 1 0 1 0 1
10, 21 0 1 0 0 0
21, 30 1 0 1 0 0
30, 2, 41 0 1 0 1 0
43, 50 0 0 1 0 1
50, 41 0 0 0 1 0

Both columns hold the same graph. The list stores 14 numbers — two per edge. The matrix stores 36, and 22 of them are zeros standing for edges that do not exist. On six nodes that gap is small. On a social network with a million users and thirty friends each, the list holds 60 million entries and the matrix would need a million squared. That is the whole argument, and it is why the list is the default.

Now run BFS from node 0. Each row below is one node coming out of the queue. The boxes are the queue contents after that node was taken and its neighbours added, left box first — and the rose box is the front, the node that comes out next. A dot means the slot is 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 of its neighbours in at once, so 1, 3 and 5 all come out before anything two edges away is even discovered. That is what makes BFS level order: everything at distance 1 is sitting in the queue before the first node at distance 2 arrives. Nodes 2 and 4 are the only two at distance 2, and they are the last two out. Swap the queue for a stack and the newest node comes out first instead — the run stops fanning out and starts walking.

03 Code

One loop, two containers

The trace you just followed is ten lines of code. Here it is twice. Read the two blocks against each other: apart from the name on line 1 and the two comments, they differ on line 3 and line 5, in one word each, and nowhere else. BFS and DFS are not two algorithms you memorise separately. They are one algorithm with two choices of container.

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

Only the container changes. Line 3 builds a Queue in one and a Stack in the other, and line 5 takes from the front in one and the top in the other. 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, because a queue returns the oldest thing you put in and a stack returns the newest.

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. Move the marking to pop time and you must also skip a node that comes out already done — the visit order still comes out right, and every edge is still looked at once, so the time stays O(V + E). What breaks is memory: a node can now be pushed once for every neighbour that finds it, so the frontier holds up to O(E) entries instead of O(V). On six nodes joined to each other that is 16 pushes instead of 6.

A stack hands the neighbours back in reverse. adj[0] is [1, 3, 5], so BFS reaches 1 first. The stack version pushes 1, then 3, then 5, and 5 is now on top — so from node 0 it goes to 5 first and then walks 0 → 5 → 4 → 3 → 2 → 1, right round the ring. Recursive DFS taking the list in order would reach 1 first instead and give 0 1 2 3 4 5.

The stack version is not just 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 and the stack gives 3 4 5 2 1 0, but no recursive DFS can produce that — standing on 5 with 0 not yet in the order, recursion is obliged to go deeper into 0, and the stack version is not, because 0 was already marked back at 3. Both traversals are correct: each reaches every node exactly once and each walks depth-ward before it fans out. They are simply not the same order, and flipping the neighbour list does not fix it in general. If you specifically need the recursive order from a loop, mark on pop instead, skip nodes already done, and push each neighbour list reversed — that one reproduces it exactly.

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). Nothing has disappeared — the frontier is now the pile of pending call frames, so the depth of the graph 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 never needs an adjacency list at all — the neighbours of cell (r, c) are the four cells around it, so adj[node] becomes four offsets with a bounds check. 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
On an unweighted graph BFS gives shortest paths, DFS does notThe level at which BFS first reaches a node is the fewest edges to it. Write dist[nb] = dist[node] + 1 at push time and the answer costs nothing extra. A node's DFS depth means nothing. Once edges carry weights neither one is a shortest path — that is Dijkstra.
On an adjacency list both cost O(V + E)Every node enters the frontier once and every edge is looked at once from each end. On this lesson's graph that is 6 nodes taken and 14 edge checks — identical for BFS and DFS. Only the order differs. On a matrix both become O(V²), as the row above says.
The frontier is the memory billO(V) in the worst case either way, and the console prints the peak for whichever graph you load. Do not confuse the explicit stack with recursion depth: on the star preset queue and stack both peak at 5, and on the chain 0-1, 1-2, 2-3, 3-4, 4-5 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 set of 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 — its frontier is always an explicit queue on the heap. If you want depth-first order on a graph that deep, write the explicit-stack version rather than the recursion.

Use something else when…

SituationBetter choiceWhy
You need the order calls enter and leave — directed-cycle detection, or a topological order read off finish timesRecursive DFSNeither the queue nor the push-marking stack produces entry and exit times; recursion gives them for free. There are other routes to the same answers — a topological order also falls out of BFS by repeatedly taking a node of indegree zero — but they are different algorithms, not this loop.
You ask whether two nodes are connected over and over, with edges arriving as you goUnion-findIt answers repeated queries in near-constant time with no traversal at all, and merges components as the edges arrive. For one question on a fixed graph, a single traversal is simpler and just as fast.
Edges carry different weightsDijkstraBFS counts edges, not cost, so it will hand you a two-edge path that is more expensive 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) instead of O(deg u).
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: a distance array, a parent array, a component counter, or four grid offsets.

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 a set of edges joining pairs of them. A tree is a graph with two restrictions: it is connected and it has no cycles, so there is exactly one path between any two nodes. Drop those and you get cycles and multiple paths between the same pair, which is exactly why graph traversal needs a visited set. Walking a rooted tree gets away without one because its child pointers go one way only; graph edges run both ways, so you can always arrive back where you have already been.
Adjacency list or adjacency matrix — which do you use?
Adjacency list, almost always. It costs O(V + E) memory against the matrix at O(V²), and real graphs are sparse — this lesson's six-node 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) against the list's O(deg u).
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; leave it out and you have built a directed graph. Creating all V lists up front matters because a node with no edges never appears in the edge list and would otherwise be missing from the result.
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. On this lesson's graph 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 exactly 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 whether or not they are edges.
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 it takes any node at distance d + 1, so the first time it reaches a node is by the fewest possible edges. Be precise about the order if you are asked: nodes at distance d + 1 are discovered earlier than that, while distance-d nodes are still sitting in the queue — what BFS never does is take one out early. Record dist[nb] = dist[node] + 1 at push time and you have the answer with no second pass. DFS commits to one branch first, so it can reach a node down a five-edge path that also happens to sit one edge from the start. Neither helps once edges have weights — that is Dijkstra.
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 is still right and every edge is still looked at once, so the time is still O(V + E). What it costs is memory: a node can then be pushed once for every neighbour that finds it, so the frontier grows to O(E) instead of O(V) — 16 pushes instead of 6 on six nodes all joined to each other. Say that distinction 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, 0 pushes 1 again, and the frontier grows forever. Load the acyclic “A tree · no cycles” preset in the console above and exactly the same thing would happen. Rooted tree traversal escapes without a visited set only because child pointers go one way, so you never walk back to a parent. A directed graph keeps terminating as long as it stays acyclic, and hangs the moment it has a cycle.
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, but they are genuinely different orders 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 goes to 5 first here while recursive DFS goes to 1 first. The real half: marking at push time claims a node the moment anyone finds it, so the iterative walk can produce orders no recursive DFS could — start at node 3 in the console above and the stack gives 3 4 5 2 1 0, which recursion cannot, because standing on 5 with 0 still unvisited it is obliged to descend into 0. If you need the recursive order out of a loop, mark on pop, skip nodes that come out already done, and push each neighbour list reversed. And for entry and exit times — directed-cycle detection, or a topological order by finish time — 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; the only difference is queue or stack.
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 — for one question on a fixed graph, a single traversal is simpler. 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; the rest are the same loop with a smarter frontier.

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. Every problem here is solvable with the ten lines from section 03 and a little bookkeeping — nothing needs an algorithm this page has not shown you.

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 on a large graph that is most of the saving. And s equal to t has to come back true even when s appears in no edge at all, which is easy to miss if you only ever test t at the moment you push it.
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, and whether s ever gets there.

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 itself costs O(n²) even on a graph with three edges — the matrix charges you its O(V²) whatever you do with it, and the sparse win only starts afterwards. And if the matrix is not symmetric it was never an undirected graph, and what you build will not be one either.
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 because the answer must come back as names. 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 the code in 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. On this lesson's graph BFS 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. The thing you need is destroyed the moment a node leaves the frontier.
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.