Breadth-first

Visits vertices level by level from a start vertex.

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

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, the ones a single hop away first, as a network scan would.

Use it in Go

it, err := traverse.NewBreadthFirstIterator(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

• Depth-first: Follows one path as deep as it can, then continues from the most recently found 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