Closest-first

Visits vertices in order of their distance from a start vertex, nearest first.

Time complexity O(E log V), gograph function traverse.NewClosestFirstIterator.

Downtown grid

Twenty intersections on a downtown street grid. Streets go both ways, Market is closed to cars between 2nd and 3rd, and each edge is the travel time in minutes.

A directed, weighted graph with 20 vertices and 60 edges.

List the intersections you can reach from Pine & 1st, nearest by travel time first.

Use it in Go

it, err := traverse.NewClosestFirstIterator(g, "Pine & 1st")
if err != nil {
	return err
}
for it.HasNext() {
	fmt.Println(it.Next().Label())
}

Example graphs

• School run, 6 vertices and 13 edges
• Delivery area, 8 vertices and 12 edges
• Downtown grid, 20 vertices and 60 edges
• One-way city, 45 vertices and 88 edges
• Metro region, 100 vertices and 346 edges

More in Traversal

• Breadth-first: Visits vertices level by level from a start vertex.
• Depth-first: Follows one path as deep as it can, then continues from the most recently found vertex.
• Random walk: Moves from a start vertex to a random out-neighbor again and again, with heavier edges more likely.

All algorithms