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.
Campus network
A hundred switches, servers and computers in ten buildings of a university campus, A to J. Each id is a building letter and a number, so D7 is number 7 in building D. A is the data center, where the core switches A1 and A2 link to the main switch of every other building, always number 1. The larger buildings have more switches between the main switch and the computers, and two pairs of neighboring buildings also have a direct link.
An undirected graph with 100 vertices and 114 edges.
Trace the campus network from the core switch A1, following each link as deep into a building as it goes before going back.
From A1, depth-first visits 100 vertices: A1, A2, A3, A5, A6, A7, A8, A9, A10, A4, and so on to J6. It met 99 tree edges and 15 back edges.
Step by step
- Start at A1. Discover it at time 1, and it begins the search path.
- A1 to A2 leads to a new vertex, so it is a tree edge. Discover A2 at time 2, and it joins the search path.
- A2 to A1 leads to A1, which is still on the search path, but it is the tree edge A2 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.
- A2 to A3 leads to a new vertex, so it is a tree edge. Discover A3 at time 3, and it joins the search path.
- A3 to A1 leads to A1, which is still on the search path, so it is a back edge. The path from A1 to A3 and this edge make a loop.
- A3 to A5 leads to a new vertex, so it is a tree edge. Discover A5 at time 4, and it joins the search path.
210 more steps lead to the last one:
- Done. Depth-first discovered 100 vertices from A1. It met 99 tree edges and 15 back edges.
Use it in Go
for ev := range traverse.DFSEvents(g, "A1") {
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.