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.

Import cycles

Eighteen packages of a Python web app. Each edge is an import, and some packages import each other in a loop.

A directed graph with 18 vertices and 30 edges.

Follow the imports from main one chain at a time, and sort each import into the four kinds: which ones lead back into the chain being followed, and so form a loop?

From main, depth-first visits 18 vertices: main, cli, config, utils, logging, db, cache, models, api, handlers, and so on to middleware. It met 17 tree edges, 5 back edges, 3 forward edges and 5 cross edges.

Step by step

  1. Start at main. Discover it at time 1, and it begins the search path.
  2. main to cli leads to a new vertex, so it is a tree edge. Discover cli at time 2, and it joins the search path.
  3. cli to config leads to a new vertex, so it is a tree edge. Discover config at time 3, and it joins the search path.
  4. config to utils leads to a new vertex, so it is a tree edge. Discover utils at time 4, and it joins the search path.
  5. utils to logging leads to a new vertex, so it is a tree edge. Discover logging at time 5, and it joins the search path.
  6. logging to utils leads to utils, which is still on the search path, so it is a back edge. The path from utils to logging and this edge make a loop.

43 more steps lead to the last one:

  1. Done. Depth-first discovered 18 vertices from main. It met 17 tree edges, 5 back edges, 3 forward edges and 5 cross edges.

Use it in Go

for ev := range traverse.DFSEvents(g, "main") {
	if ev.Edge != nil {
		fmt.Println(ev.Kind, ev.Edge.Source().Label(), ev.Edge.Destination().Label())
	}
}

Example graphs

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.

All algorithms