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.

Karate club

The 34 members of a university karate club, numbered 1 to 34 as in the study. Each edge joins two members who also spent time together outside the club's classes and meetings. A dispute between the instructor (1) and an officer (34) split the club in two, and most members sit near the side they joined.

An undirected graph with 34 vertices and 78 edges.

Starting with the instructor, member 1, follow a chain of members who spent time together as far as it goes, then go back and try the next, until everyone linked to the instructor is found.

Use it in Go

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