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.

Maze

A maze of 30 cells in five rows, A to E, and six columns, 1 to 6, so C4 is row C, column 4. Each edge is an open passage between two cells. The way from A1 to E6 winds through most of the maze, and two short loops give a few cells a second route.

An undirected graph with 30 vertices and 31 edges.

Walk the maze from A1 the way a person would: follow one passage until it ends, then go back to the last fork and try the next.

Use it in Go

it, err := traverse.NewDepthFirstIterator(g, "A1")
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