Why search?
Many questions about a graph come down to "what can I reach from here?":
- Is this road network connected, or are some towns cut off?
- What's the fewest number of flights from Istanbul to Lima?
- Can this puzzle be solved from this position?
- Which web pages can be found by following links from a homepage?
For a small drawing, your eyes answer instantly. A computer working on a graph with millions of vertices needs a systematic method: one that visits every reachable vertex, never gets stuck going round in circles, and never visits the same vertex twice. Both methods in this unit follow the same basic recipe:
- Mark the starting vertex as discovered.
- Repeatedly pick a discovered vertex, look along its edges, and mark any undiscovered neighbours as discovered.
- Stop when there's nothing left to look at.
The only difference between them is which discovered vertex you pick next. That one choice gives them completely different personalities.
Breadth-first search
Breadth-first search (BFS) explores like a ripple spreading across a pond. It first visits everything 1 step from the start, then everything 2 steps away, then 3, and so on.
To do this it keeps a queue, a waiting line where the first to arrive is the first to be served. Newly discovered vertices join the back of the queue; the next vertex to explore is always taken from the front. Since vertices at distance 1 are all discovered before any at distance 2, they're all explored first too.
Swipe or scroll sideways to step through.
Start at S
S gets distance 0. Queue: S.
Visit S
Take S from the front of the queue. Its new neighbours A and B get distance 1 and join the back. Queue: A, B.
Visit A
Take A. S and B are already known; C is new, so it gets distance 1 + 1 = 2. Queue: B, C.
Visit B
Take B. Only D is new: distance 2. Queue: C, D. Everything at distance 1 is now finished.
Visit C, then D
Take C: E is new, distance 3. Then take D: its neighbours B, C, E are all known, so nothing happens. Queue: E.
Visit E, then F
E discovers F (distance 4); F discovers nothing. The queue is empty: done. The teal edges form the BFS tree, and each path in it from S is a shortest path.
being exploredwaiting in the queuefinisheddiscovery edge
The pink numbers are distances from S. BFS calculates them for free: when vertex x discovers a new neighbour y, set distance(y) = distance(x) + 1. Because BFS explores in order of distance, the first time it finds a vertex is always along a shortest route. Each vertex remembers which vertex discovered it, and following those links back to S traces a shortest path.
Breadth-first search in brief
Put the start in a queue. Repeat: take the vertex at the front; for each neighbour not yet discovered, record its distance and its discoverer, then add it to the back of the queue. Stop when the queue is empty.
Example: "people you may know"
A social network suggests friends by looking at people at distance exactly 2 from you: friends of your friends who aren't your friends yet. That's the first two layers of a BFS from your profile. Ranking them by how many mutual friends you share gives the familiar suggestion list.
Watch out
BFS finds shortest paths only when every edge counts the same, as one step. If edges have different lengths, like roads measured in kilometres, a route with more edges can be shorter. That needs the algorithms of Unit 5.
Depth-first search
Depth-first search (DFS) explores like a person in a cave system with a ball of string. Keep going forward into unexplored territory for as long as you can. When you hit a dead end, follow the string back to the last junction with an unexplored passage and try that. The Greek hero Theseus is said to have used exactly this trick to find his way back out of the Minotaur's labyrinth.
The ball of string is a stack: like a pile of plates, the last one put on is the first one taken off. Going forward pushes a vertex onto the stack; backtracking pops it off.
Swipe or scroll sideways to step through.
Start at S
Start at S. Stack (the route back): S.
Go deep: S → A → B
From S, go to the first unvisited neighbour, A. From A, the first unvisited neighbour is B. Keep going. Stack: S, A, B.
Deeper: → D → C
B's only new neighbour is D. D's first new neighbour is C. Stack: S, A, B, D, C.
Deeper: → E → F
C → E → F. F has no unvisited neighbours: a dead end. Now backtrack: pop F, then E, D, C… none of them has an unvisited neighbour left.
Done
Back at S, with nothing left unvisited. The DFS tree (teal) is one long path, very different from the short, bushy BFS tree.
Same graph, same start, same rule of "never revisit", yet a totally different exploration. The DFS tree reaches F by the long way round (S, A, B, D, C, E, F: six steps) even though F is only 4 steps from S. DFS is not a shortest-path method. What it's good at is following one possibility all the way to its end before trying the next.
Depth-first search in brief
From the current vertex, move to any undiscovered neighbour and repeat from there. If there's none, step back to the previous vertex on the route. Stop when you've stepped back to the start and it has no undiscovered neighbours left.
Try it. Run BFS and DFS on the same graph starting from F instead of S, always choosing neighbours in alphabetical order. In what order does each method visit the vertices?
Show answer
BFS from F: F, then E (distance 1), then C, D (distance 2), then A, B (distance 3), then S (distance 4). Order: F, E, C, D, A, B, S.
DFS from F: F → E → C (E's first neighbour alphabetically) → A (C's first new neighbour) → B → D (B's first new neighbour is D, since S comes after D alphabetically) → D has no new neighbours, so back to B → S. Order: F, E, C, A, B, D, S.
BFS or DFS?
| Breadth-first search | Depth-first search | |
|---|---|---|
| Picture | A ripple spreading outwards | An explorer with a ball of string |
| Keeps a… | Queue (first in, first out) | Stack (last in, first out) |
| Visits | Nearest vertices first | As far as possible along one route first |
| Finds shortest paths? | Yes, counting edges | No |
| Its tree tends to be | Short and bushy | Long and thin |
| Great for | Distances, "degrees of separation", nearest anything | Mazes, puzzles, detecting cycles, ordering tasks |
Both visit every vertex reachable from the start exactly once and look along every edge at most twice, once from each end. So both take time proportional to the size of the graph, which makes them very fast even on huge networks.
Example: counting components
To count the components of a graph (Unit 2), run a search from any vertex: it discovers exactly that vertex's component. Then pick any vertex not yet discovered and search again: a second component. Repeat until every vertex has been discovered. The number of searches you started is the number of components.
Example: the paint bucket
The "fill" tool in a paint program treats every pixel as a vertex joined to the pixels above, below, left and right of it that have the same colour. Clicking runs a search from that pixel and recolours everything it reaches. That's why the fill leaks out through a one-pixel gap in an outline: the gap is an edge to the outside.
Mazes and puzzles
Any maze is a graph in disguise. Make each room (or junction) a vertex, and each doorway (or corridor) an edge.
The maze
The same maze as a graph
Once the maze is a graph, the earlier methods take over. DFS is exactly how you'd explore it on foot with a ball of string. BFS is what you'd do with an unlimited team of explorers who split up at every junction; the first to reach the exit has found a shortest route.
Puzzles as graphs
The same idea works for puzzles where the "rooms" aren't places but situations. A classic: a farmer must ferry a wolf, a goat and a cabbage across a river. The boat holds the farmer plus one item. The wolf can't be left alone with the goat, and the goat can't be left alone with the cabbage.
Make each safe arrangement (who's on which bank) a vertex, and join two arrangements if one boat trip turns one into the other. Now "solve the puzzle" means "find a path from everyone on the left bank to everyone on the right bank". BFS finds that the shortest solution takes 7 crossings: take the goat over; come back; take the wolf over; bring the goat back; take the cabbage over; come back; take the goat over. The same method solves sliding-tile puzzles, the Rubik's cube (in principle; its graph has about 43 quintillion vertices) and the moves of game-playing programs.
Try it. A puzzle graph has 1,000 vertices. A BFS from the starting position never reaches the goal position. What does that tell you?
Show answer
The goal is in a different component from the start, so the puzzle is impossible from that starting position, however cleverly you play. BFS proved it by exhausting every reachable situation. (The famous "15 puzzle" with two tiles swapped is like this: exactly half of all arrangements can't be reached.)
Tasks with an order: DAGs
Some tasks must happen before others. You put on socks before shoes and a shirt before a tie. Draw an arrow from each task to every task that must wait for it, and you get a directed graph.
For a schedule like this to be possible, there must be no directed cycle. If A must come before B, B before C and C before A, nothing can ever start. A directed graph with no directed cycles is called a directed acyclic graph, or DAG for short.
DAGs show up wherever things depend on other things:
- University courses and their prerequisites.
- Recipes: you can't ice the cake before baking it, but you can make the icing while it bakes.
- Spreadsheets: a cell's formula depends on other cells. The program must recalculate cells in an order where every cell comes after the cells it uses. A "circular reference" error is a directed cycle.
- Building software, where each file must be compiled after the files it relies on.
- Family trees: arrows from parent to child can never form a cycle.
Topological sorting
A topological order of a DAG is a list of all its vertices in which every arrow points forwards: each task comes after everything it depends on. Here is one for getting dressed:
How do you find such an order? One simple method, published by Arthur Kahn in 1962, repeatedly takes a task that nothing is waiting on:
- Find a vertex with no arrows coming into it. (A DAG always has one. Follow arrows backwards from anywhere; without cycles you must eventually get stuck.)
- Write it down next in the list, and delete it with its outgoing arrows.
- Repeat until no vertices are left.
| Step | Ready to go (nothing waiting) | Take | Newly ready |
|---|---|---|---|
| 1 | Underwear, Socks, Shirt, Watch | Underwear | Trousers |
| 2 | Socks, Shirt, Watch, Trousers | Socks | none (Shoes still waits for Trousers) |
| 3 | Shirt, Watch, Trousers | Shirt | Tie |
| 4 | Watch, Trousers, Tie | Trousers | Shoes, Belt |
| 5 | Watch, Tie, Shoes, Belt | Shoes | none |
| 6 | Watch, Tie, Belt | Belt | none (Jacket still waits for Tie) |
| 7 | Watch, Tie | Tie | Jacket |
| 8 | Watch, Jacket | Jacket | none |
| 9 | Watch | Watch | none |
When there's a choice, any choice works, so most DAGs have many topological orders. If the method ever gets stuck, with vertices left but none of them free of incoming arrows, then the graph has a directed cycle and no valid order exists. So the same method also detects impossible schedules.
DFS gives another way: run DFS, note the moment each vertex is finished (when you backtrack out of it for the last time), and list the vertices in reverse order of finishing. Every task finishes after everything that depends on it, so reversing the list puts it before them.
Try it. A course has modules with these prerequisites: Algebra before Calculus; Algebra before Statistics; Calculus before Physics; Statistics before Machine Learning; Calculus before Machine Learning. Give a valid order. Then suppose someone adds "Machine Learning before Algebra". What happens?
Show answer
One valid order: Algebra, Calculus, Statistics, Physics, Machine Learning. (Algebra, Statistics, Calculus, Machine Learning, Physics also works.)
Adding "Machine Learning before Algebra" creates the directed cycle Algebra → Calculus → Machine Learning → Algebra. Now no valid order exists: Kahn's method gets stuck immediately, because every module is waiting for another one.
Practice set
Mixed questions covering the whole unit. Try each one before opening the answer.
1. In a BFS from vertex S, vertex X was discovered while exploring a vertex at distance 4. What is the distance from S to X?
Show answer
5. BFS gives a newly discovered vertex the distance of its discoverer plus one, and the first discovery is always along a shortest route.
2. A BFS on a connected graph with 50 vertices builds a BFS tree. How many edges does that tree have?
Show answer
49. Every vertex except the start is discovered exactly once, along one edge, and those edges form a spanning tree.
3. Your phone's contacts app wants to show everyone within 3 "introductions" of you. Should it use BFS or DFS?
Show answer
BFS, stopping after layer 3. DFS might wander down one long chain of friends-of-friends and could label someone as far away when there's actually a short route to them.
4. Why must every DAG have at least one vertex with no incoming arrows?
Show answer
Start anywhere and keep walking backwards along incoming arrows. If every vertex had an incoming arrow, you could do this forever. But there are only finitely many vertices, so eventually you'd revisit one, and the route between the two visits would be a directed cycle. A DAG has none, so the backwards walk must get stuck at a vertex with no incoming arrows.
5. How many different topological orders does a DAG with 4 vertices and no arrows have? And one whose arrows form a single chain A → B → C → D?
Show answer
With no arrows, any order works: 4 × 3 × 2 × 1 = 24. With the chain, only 1: A, B, C, D.
6. A web crawler starts at one homepage and follows links. Explain why it must keep a list of pages it has already seen.
Show answer
The web is full of directed cycles: page A links to B, which links back to A. Without remembering which pages have been discovered, the crawler would go round such cycles forever. Marking vertices as discovered is exactly what makes BFS and DFS stop.
Summary and glossary
- Graph search explores everything reachable from a start, marking vertices as discovered so nothing is visited twice.
- Breadth-first search uses a queue and explores in layers. It finds shortest paths when every edge counts as one step.
- Depth-first search uses a stack, going as deep as possible and then backtracking. It's the "ball of string" method for mazes.
- Both run in time proportional to the size of the graph, and both can count components or show that a goal is unreachable.
- Puzzles become graphs when situations are vertices and moves are edges.
- A DAG has no directed cycles. Its vertices can be put in a topological order where every arrow points forwards.
- Breadth-first search
- Exploring a graph layer by layer from the start, using a queue.
- Depth-first search
- Exploring as far as possible along each route before backtracking, using a stack.
- Queue
- A list where items join at the back and leave from the front.
- Stack
- A pile where the last item added is the first removed.
- BFS / DFS tree
- The edges along which each vertex was first discovered.
- State graph
- A graph whose vertices are situations in a puzzle and whose edges are moves.
- DAG
- A directed graph with no directed cycles.
- Topological order
- A list of a DAG's vertices with every arrow pointing forwards.