Depth-first search follows one path as far as it goes, backs up to the last junction, and takes the next turning until everything reachable has been visited.
Strategy
Depth-first graph traversal with backtracking
Follow one path to its end, then unwind to the last junction that still has a turning left.
- Descend: move to the first unseen neighbor.
- Backtrack: at a dead end, return to the node you came from.
- Repeat: take the next unseen neighbor there until nothing is left.
Press Step to follow one edge. The stack on the right is the chain of calls you are inside, and it shrinks every time a branch runs out.
Purpose
Visit everything reachable from a starting node, following one path as far as it goes.
Input
A graph as map[string][]string and the node to start from.
Output
A []string of nodes in the order they were visited.
Constraints
- Mark a node on the way in, or a cycle sends the recursion round forever.
- Recursion depth grows with the longest path, so a huge graph wants an explicit stack.
- The visit order depends on how each node's neighbors are listed.
How depth-first search works
Think of walking a maze with your hand on the left wall. You keep going down a corridor until you hit a dead end, back up to the last junction you had a choice at, and take the next turning. Eventually you have walked the whole thing.
It suits questions about whole paths rather than short ones: finding a route out, spotting a cycle, or working out which parts of a network connect to which.
graph[u].What depth-first search keeps track of
| Name | Type | What it is for |
|---|---|---|
| graph | map[string][]string | Each node, and the nodes it connects to. |
| start | string | The node you begin from. |
| visited | map[string]bool | Nodes already seen, so you never loop back round. |
| order | []string | The nodes in the order you reached them. |
| walk | func(string) | The function that visits one node and calls itself on its neighbors. |
Walk through it
1 Start with a graph and a node
The same shape breadth-first search takes: a map from each node to its neighbors.
graph := map[string][]string{
"A": {"B", "C"},
"B": {"A", "D", "E"},
"C": {"A", "F"},
"D": {"B"},
"E": {"B"},
"F": {"C"},
}
order := dfs(graph, "A")2 Turn back if you have been here
Graphs loop. Without this check A sends you to B, which sends you straight back to A, forever.
if visited[node] {
return
}3 Mark the node and record it
Note that you have been here before going anywhere else.
visited[node] = true
order = append(order, node)4 Go all the way down the first neighbor
Call the same function on each neighbor in turn. The first call runs to its own dead end before the second one starts, which is what makes this depth-first.
for _, n := range graph[node] {
walk(n)
}5 Unwind the calls
Each finished call hands control back to the one that made it, which then tries its next neighbor. That is the backing-up part of walking a maze.
var walk func(string)
walk = func(node string) {
// check, mark, then walk each neighbor
}
walk(start)The whole program
Put it together and you get the nodes in the order you walked them, one full branch at a time.
package main
import "fmt"
func dfs(graph map[string][]string, start string) []string {
visited := map[string]bool{}
var order []string
var walk func(string)
walk = func(node string) {
if visited[node] {
return
}
visited[node] = true
order = append(order, node)
for _, n := range graph[node] {
walk(n)
}
}
walk(start)
return order
}
func main() {
graph := map[string][]string{
"A": {"B", "C"},
"B": {"A", "D", "E"},
"C": {"A", "F"},
"D": {"B"},
"E": {"B"},
"F": {"C"},
}
fmt.Println(dfs(graph, "A"))
}$ go run main.go
[A B D E C F]