Visiting everything, once
A graph is a set of nodes joined by edges. The most basic thing to do with one is to start somewhere and visit every node you can reach.
That one operation answers a lot of questions. Is there a route from A to H? Which web pages can be reached from this one? Which cells does this paint-bucket fill touch? Which files does this program depend on?
A list can be walked from start to end. A graph has no start and no end, and it can have loops. So two things are needed:
- A "seen" set, so that no node is visited twice and loops do not trap you.
- A to-do list of nodes that have been discovered but not yet visited.
The surprising part: the whole difference between the two famous methods is which end of the to-do list you take from.
Breadth-first search (BFS)
The to-do list is a queue. Take from the front, add to the back. The node that has waited longest goes next.
Queue (front on the left)
Visited, in order
Start. Breadth-first: keep a queue of nodes to visit. Take from the front, add new discoveries at the back. Start with A in the queue.
- Visited
- 0 / 8
The order was A, B, C, D, E, F, G, H. Everything one step from A, then everything two steps away, then three. It spreads out like a ripple in water.
from collections import deque
def bfs(graph, start):
seen = {start}
queue = deque([start])
while queue:
node = queue.popleft() # oldest first
visit(node)
for neighbour in graph[node]:
if neighbour not in seen:
seen.add(neighbour)
queue.append(neighbour)Depth-first search (DFS)
The to-do list is a stack. Take from the top, add to the top. The node discovered most recently goes next.
Stack (top on the right)
Visited, in order
Start. Depth-first: keep a stack of nodes to visit. Take from the top, add new discoveries on top. Start with A on the stack.
- Visited
- 0 / 8
The order was A, B, D, E, H, F, C, G. It went down one branch as far as it could, and only came back for C at the end.
def dfs(graph, start):
seen = {start}
stack = [start]
while stack:
node = stack.pop() # newest first
visit(node)
for neighbour in reversed(graph[node]):
if neighbour not in seen:
seen.add(neighbour)
stack.append(neighbour)Change popleft() to pop() and a breadth-first search becomes a depth-first one. See Stacks and Queues.
DFS is often written with recursion instead. The call stack then does the job of the stack.
def dfs(graph, node, seen):
seen.add(node)
visit(node)
for neighbour in graph[node]:
if neighbour not in seen:
dfs(graph, neighbour, seen)Try both
Queue (front on the left)
Visited, in order
Start. Breadth-first: keep a queue of nodes to visit. Take from the front, add new discoveries at the back. Start with A in the queue.
- Visited
- 0 / 8
What they cost
Both visit each node once and look along each edge once (twice if edges go both ways). The time is the number of nodes plus the number of edges. Neither is faster than the other.
They differ in memory:
- BFS holds a whole "ring" of nodes at once. In a wide graph that can be a large share of all the nodes.
- DFS holds one path from the start, plus the branches left to try. In a deep graph that can be long, and the recursive form can overflow the stack.
Which to use
| You want | Use | Why |
|---|---|---|
| The shortest route, in number of steps | BFS | It reaches nodes in order of distance |
| Everything within k steps | BFS | Stop after k rings |
| To know whether a route exists at all | Either | Both visit everything reachable |
| To detect a loop | DFS | A loop shows up as meeting a node that is still on the current path |
| An order that respects dependencies | DFS | A node is finished only after everything it leads to |
| To explore all choices in a puzzle, undoing as you go | DFS | Going deep and backing up is exactly backtracking |
| To solve a maze | Either | DFS finds a way out. BFS finds the shortest |
Example
Friends of friends
A social network wants to suggest "people you may know": everyone exactly two connections away from you.
BFS is the natural fit. The first ring is your friends. The second ring is their friends who are not already yours. Stop there. DFS would wander far along one chain of acquaintances before coming back.
The mistake everyone makes once
Forgetting the "seen" set. In a tree it does not matter, since there is only one way to reach each node. In a graph with a loop, A leads to B, B leads back to A, and the search never ends.
Mark a node as seen when you add it to the to-do list, not when you take it out. Otherwise the same node can be added many times before its turn comes.
Key takeaways
- Traversal means visiting every reachable node once, using a to-do list and a set of nodes already seen.
- Breadth-first search uses a queue and spreads out in rings, nearest nodes first.
- Depth-first search uses a stack, or recursion, and follows one path to its end before backing up.
- BFS finds the route with the fewest steps. DFS suits loops, dependency order and backtracking.
- Both take time proportional to nodes plus edges. Without a seen set, a loop makes either run forever.