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.

Metro region

A hundred towns, T1 to T100, where T stands for town, numbered row by row from the top left with ten to a row. Two fast motorways cross at T45: one runs from T41 to T50, the other through T5, T15 and on down to T95. Local roads join neighboring towns, a few of them one way, and each edge is the travel time in minutes.

A directed, weighted graph with 100 vertices and 346 edges.

List the towns you can reach from T45, where the two motorways cross, nearest by travel time first.

Use it in Go

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