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.

One-way city

Forty-five intersections, I1 to I45, where I stands for intersection, numbered row by row from the top left with nine to a row. Most streets are one way, and the outer streets form a clockwise loop. Only the middle row (I19 to I27) and the middle column (I5, I14, I23, I32 and I41) go both ways, and each edge is the travel time in minutes.

A directed, weighted graph with 45 vertices and 88 edges.

List the intersections you can reach from I23 in the middle of town, nearest by travel time first, when most streets are one way.

Use it in Go

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