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.

Home network

A router and the devices connected to it.

An undirected graph with 6 vertices and 6 edges.

Find every device the router can reach by following one cable as far as it goes before going back.

Use it in Go

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