Depth-first

Follows one path as deep as it can, then continues from the most recently found vertex.

Time complexity O(V+E), gograph function traverse.NewDepthFirstIterator.

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.

Use it in Go

it, err := traverse.NewDepthFirstIterator(g, "Core")
if err != nil {
	return err
}
for it.HasNext() {
	fmt.Println(it.Next().Label())
}

Example graphs

• Home network, 6 vertices and 6 edges
• Office network, 13 vertices and 16 edges
• Maze, 30 vertices and 31 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.

All algorithms