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.
Karate club
The 34 members of a university karate club, numbered 1 to 34 as in the study. Each edge joins two members who also spent time together outside the club's classes and meetings. A dispute between the instructor (1) and an officer (34) split the club in two, and most members sit near the side they joined.
An undirected graph with 34 vertices and 78 edges.
Starting with the instructor, member 1, follow a chain of members who spent time together as far as it goes, then go back and try the next, until everyone linked to the instructor is found.
From 1, depth-first visits 34 vertices: 1, 2, 3, 4, 8, 13, 14, 34, 9, 31, and so on to 12. It met 33 tree edges and 45 back edges.
Step by step
- Start at 1. Discover it at time 1, and it begins the search path.
- 1 to 2 leads to a new vertex, so it is a tree edge. Discover 2 at time 2, and it joins the search path.
- 2 to 1 leads to 1, which is still on the search path, but it is the tree edge 2 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.
- 2 to 3 leads to a new vertex, so it is a tree edge. Discover 3 at time 3, and it joins the search path.
- 3 to 1 leads to 1, which is still on the search path, so it is a back edge. The path from 1 to 3 and this edge make a loop.
- 3 to 4 leads to a new vertex, so it is a tree edge. Discover 4 at time 4, and it joins the search path.
108 more steps lead to the last one:
- Done. Depth-first discovered 34 vertices from 1. It met 33 tree edges and 45 back edges.
Use it in Go
for ev := range traverse.DFSEvents(g, "1") {
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.