Breadth-first search (BFS)

Exploring in concentric circles

The breadth-first search (BFS) explores the graph in waves starting from a departure vertex: first all the direct neighbours, then the neighbours of the neighbours, and so on. Like a ripple on the surface of water.

Start at A :

  wave 0 :    A
  wave 1 :    B, C          (direct neighbours of A)
  wave 2 :    D, E          (new neighbours of B and C)

        (A)
        /  \
      (B)   (C)
      /       \
    (D)       (E)

The graph trap: cycles

Unlike a tree, a graph can have cycles. Without precautions, we would go round in circles indefinitely. The safeguard is essential: we keep a set of the already visited vertices, and we never process the same one twice.

The algorithm, with a queue

BFS uses a queue (FIFO), exactly like the breadth-first traversal of a tree — but augmented with a visites set.

from collections import deque

def bfs(graphe, depart):
    visites = {depart}             # (already seen, so as not to loop)
    file = deque([depart])
    ordre = []
    while file:
        s = file.popleft()         # (we take out the oldest)
        ordre.append(s)
        for voisin in graphe[s]:
            if voisin not in visites:
                visites.add(voisin)     # (mark BEFORE enqueuing)
                file.append(voisin)
    return ordre

Step-by-step walkthrough

On the graph A: B,C — B: A,D — C: A,E — D: B — E: C, starting at A:

  file        visites          action
  [A]         {A}              take out A, enqueue B, C
  [B, C]      {A,B,C}          take out B, enqueue D
  [C, D]      {A,B,C,D}        take out C, enqueue E
  [D, E]      {A,B,C,D,E}      take out D (D->B already seen)
  [E]         {A,B,C,D,E}      take out E (E->C already seen)
  []          -                queue empty : done

  visit order :   A  B  C  D  E

The property that makes BFS valuable

In an unweighted graph, BFS finds the shortest path (in number of edges) from the start to each vertex. Since it explores wave by wave, a vertex reached at wave k is necessarily k edges from the start — it is impossible to do shorter. This is what is used, for example, to find the "degree of separation" between two people on a social network.

In summary

BFS explores a graph in successive waves using a queue and a set of visited vertices (essential because of cycles). It visits the vertices in increasing distance from the start, which allows it to find the shortest path in number of edges.