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.

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.

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