Depth-first
Follows one path as deep as it can, then backs up to the last vertex with a neighbor left to try, and sorts every edge it meets into four kinds.
Time complexity O(V+E), gograph function traverse.DFSEvents.
traverse.DFS and traverse.NewDepthFirstIterator keep a stack and mark a vertex when they push it, so their order can differ from this one.
How it works
Depth-first search goes from the vertex it is at to a neighbor it hasn't seen, and from there to the next, as deep as it can. The vertices it has gone through form the search path. When the vertex at the end of the path has no neighbor left to try, the search finishes it and backs up one vertex. Each vertex gets a discovery time when the search enters it and a finish time when it leaves, and the times of a vertex nest inside the times of the vertex it was reached from, like parentheses.
traverse.DFSEvents reports each step as an event and sorts every edge it meets into four kinds. A tree edge leads to a new vertex. A back edge leads to a vertex still on the search path, so it closes a loop. A forward edge leads to a finished vertex discovered after the one the search is at, a descendant reached another way. A cross edge leads to a finished vertex discovered before it, in another branch. An undirected graph has only tree and back edges, and the edge back to the vertex a vertex was reached from is the tree edge itself, not a back edge.
The search costs O(V+E). Use it to find everything a vertex can reach, to explore a maze one branch at a time, or for the back edges, which are how connectivity.FindCycle and the topological sorts by finish time work. The path it follows is rarely the shortest one. For the fewest edges, use Breadth-first.
Office network
Switches and rooms in a four-team office, wired through a core switch.
An undirected graph with 13 vertices and 16 edges.
Trace the wiring from the core switch: follow one cable as far as it goes, then go back to the last switch with a cable left to follow.
From Core, depth-first visits 13 vertices: Core, Sales, Uplink, Support, Support 1, Shared, Ops, Ops 1, Sales 1, Lab, and so on to Dev 2. It met 12 tree edges and 4 back edges.
Step by step
- Start at Core. Discover it at time 1, and it begins the search path.
- Core to Sales leads to a new vertex, so it is a tree edge. Discover Sales at time 2, and it joins the search path.
- Sales to Core leads to Core, which is still on the search path, but it is the tree edge Sales was discovered by, seen from the other end. On an undirected graph that isn't a back edge, so the search skips it, here and every time it comes up.
- Sales to Uplink leads to a new vertex, so it is a tree edge. Discover Uplink at time 3, and it joins the search path.
- Uplink to Support leads to a new vertex, so it is a tree edge. Discover Support at time 4, and it joins the search path.
- Support to Core leads to Core, which is still on the search path, so it is a back edge. The path from Core to Support and this edge make a loop.
25 more steps lead to the last one:
- Done. Depth-first discovered 13 vertices from Core. It met 12 tree edges and 4 back edges.
Use it in Go
for ev := range traverse.DFSEvents(g, "Core") {
if ev.Edge != nil {
fmt.Println(ev.Kind, ev.Edge.Source().Label(), ev.Edge.Destination().Label())
}
}
Example graphs
- Home network, 6 vertices and 6 edges
- Office network, 13 vertices and 16 edges
- Import cycles, 18 vertices and 30 edges
- Karate club, 34 vertices and 78 edges
- Campus network, 100 vertices and 114 edges
More in Traversal
- Breadth-first: Visits vertices level by level from a start vertex.
- Closest-first: Visits vertices in order of their distance from a start vertex, nearest first.
- Random walk: Moves from a start vertex to a random out-neighbor again and again, with heavier edges more likely.