Breadth-First Search

Breadth-first search spreads out from a starting node one ring at a time, visiting every neighbor before moving further out.

Strategy

Breadth-first graph traversal

A queue hands nodes back in the order they were found, so one ring finishes before the next begins and every node is reached first by its shortest route.

Queue: put the start node in and mark it seen.
Visit: take the oldest node off the front.
Expand: queue its unseen neighbors, then go again until the queue empties.

unseen in the queue visiting now done

Press Step to take one node off the front of the queue. Watch the ring of nodes at each distance fill in completely before the next ring starts.

Purpose

Visit everything reachable from a starting node, nearest first.

Input

A graph as map[string][]string and the node to start from.

Output

A []string of nodes in the order they were visited.

Constraints

Mark a node seen as it goes into the queue, or it lands there twice.
Every edge counts as one step. Roads with lengths need Dijkstra instead.
A node with no route from the start never appears in the result.

How breadth-first search works

Picture ripples spreading from a stone dropped in water. You visit every neighbor of where you started, then every neighbor of those, and so on outwards. Nothing two steps away gets looked at until everything one step away is done.

Because it works outwards in rings, the first time it reaches a node it has taken the shortest route there. That makes it the tool for "fewest hops" questions: social connections, maze exits, network routes.

N(u) = \{\, v \in V : (u,v) \in E \,\}

The neighbors of a node. In code this is graph[u].

L_0 = \{s\}, \quad L_{k+1} = \bigcup_{u \in L_k} N(u) \setminus \bigcup_{i \le k} L_i

Ring by ring. Each new ring is the neighbors of the last one, minus everything already seen.

What breadth-first search keeps track of

Name	Type	What it is for
graph	map[string][]string	Each node, and the nodes it connects to.
start	string	The node you begin from.
queue	[]string	Nodes waiting their turn, oldest first.
visited	map[string]bool	Nodes already queued, so none goes in twice.
order	[]string	The nodes in the order you reached them.

Walk through it

1 Start with a graph and a node

A map from each node to its neighbors is all a graph needs to be.

graph := map[string][]string{
    "A": {"B", "C"},
    "B": {"A", "D", "E"},
    "C": {"A", "F"},
    "D": {"B"},
    "E": {"B"},
    "F": {"C"},
}

order := bfs(graph, "A")

2 Put the start in the queue and mark it seen

The queue holds what is waiting. Marking a node as you queue it, rather than as you visit it, stops it being added twice.

visited := map[string]bool{start: true}
queue := []string{start}

3 Take the oldest node off the front

Taking from the front is what makes this breadth-first. Take from the back instead and you get depth-first search.

node := queue[0]
queue = queue[1:]
order = append(order, node)

4 Queue up its unseen neighbors

Each neighbor you have not met goes on the back of the queue, so it gets its turn after everything already waiting.

for _, n := range graph[node] {
    if !visited[n] {
        visited[n] = true
        queue = append(queue, n)
    }
}

5 Keep going until the queue empties

An empty queue means everything reachable has been visited.

for len(queue) > 0 {
    // take one off the front, queue its neighbors
}

The whole program

Put it together and you get the nodes in the order they were reached, closest to the start first.

package main

import "fmt"

func bfs(graph map[string][]string, start string) []string {
    visited := map[string]bool{start: true}
    queue := []string{start}
    var order []string

    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        order = append(order, node)

        for _, n := range graph[node] {
            if !visited[n] {
                visited[n] = true
                queue = append(queue, n)
            }
        }
    }
    return order
}

func main() {
    graph := map[string][]string{
        "A": {"B", "C"},
        "B": {"A", "D", "E"},
        "C": {"A", "F"},
        "D": {"B"},
        "E": {"B"},
        "F": {"C"},
    }
    fmt.Println(bfs(graph, "A"))
}

Terminal

$ go run main.go
[A B C D E F]

Previous Graph Next Topic Depth-First Search