Breadth-first

Visits vertices level by level from a start vertex.

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

traverse.BFS gives the same order without the depths, and traverse.NewBreadthFirstIterator gives it one Next at a time. path.BFSPaths returns the route with the fewest edges to each vertex, the edges the steps draw.

How it works

Breadth-first search keeps a queue of the vertices it has found but not visited yet. It takes the vertex at the front and puts each neighbor it hasn't seen at the back. So every vertex one edge from the start comes out before any vertex two edges away, and so on, one level at a time.

When every edge counts the same, that order gives the fewest edges from the start to each vertex, such as the fewest hops between two machines. gograph marks a vertex as seen when it joins the queue, so each one is visited once and the search costs O(V+E). Vertices the start can't reach are never visited.

traverse.BFS and traverse.BFSWithDepth return an iter.Seq, so a range loop can break as soon as it finds what it needs, and BFSWithDepth gives each vertex with its number of edges from the start. path.BFSPaths runs the same search and keeps the edge that first found each vertex, so PathTo on its result gives a route with the fewest edges to any vertex, start first, and false for one out of reach. When edges have different weights, the fewest edges isn't the shortest route, and Closest-first or Dijkstra gives the real distances.

Campus network

A hundred switches, servers and computers in ten buildings of a university campus, A to J. Each id is a building letter and a number, so D7 is number 7 in building D. A is the data center, where the core switches A1 and A2 link to the main switch of every other building, always number 1. The larger buildings have more switches between the main switch and the computers, and two pairs of neighboring buildings also have a direct link.

An undirected graph with 100 vertices and 114 edges.

Find every device on campus that the core switch A1 can reach, the ones fewest hops away first, as a network discovery scan would.

From A1, breadth-first visits 100 vertices: A1, A2, A3, A4, B1, C1, D1, E1, F1, G1, and so on to H9.

Step by step

  1. Start at A1. Put it in the queue.
  2. Take A1 from the front of the queue.
  3. Add A2, A3, A4, B1, C1, D1, E1, F1, G1, H1, I1 and J1, the unseen neighbors of A1, to the back of the queue.
  4. Take A2 from the front of the queue.
  5. A2 has no unseen neighbors.
  6. Take A3 from the front of the queue.

195 more steps lead to the last one:

  1. Done. Breadth-first reached 100 vertices from A1.

Use it in Go

for v, depth := range traverse.BFSWithDepth(g, "A1") {
	fmt.Println(v.Label(), depth)
}

paths, err := path.BFSPaths(g, "A1")
if err != nil {
	return err
}
route, _ := paths.PathTo("B4")
for _, v := range route {
	fmt.Println(v.Label())
}

Example graphs

More in Traversal

  • Depth-first: Follows one path as deep as it can, then backs up to the last vertex with a neighbor left to try, and sorts every edge it meets into four kinds.
  • 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