Le parcours en largeur (BFS)

Explorer en cercles concentriques

Le parcours en largeur (en anglais (Breadth-First Search), BFS) explore le graphe par vagues à partir d'un sommet de départ : d'abord tous les voisins directs, puis les voisins des voisins, et ainsi de suite. Comme une onde à la surface de l'eau.

Depart en A :

  vague 0 :   A
  vague 1 :   B, C          (voisins directs de A)
  vague 2 :   D, E          (nouveaux voisins de B et C)

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

Le piège des graphes : les cycles

Contrairement à un arbre, un graphe peut avoir des cycles. Sans précaution, on tournerait en rond indéfiniment. La parade est essentielle : on tient un ensemble des sommets déjà visités, et on ne traite jamais deux fois le même.

L'algorithme, avec une file

Le BFS utilise une file (FIFO), exactement comme le parcours en largeur d'un arbre — mais augmentée d'un ensemble visites.

from collections import deque

def bfs(graphe, depart):
    visites = {depart}             # (déjà vus, pour ne pas boucler)
    file = deque([depart])
    ordre = []
    while file:
        s = file.popleft()         # (on sort le plus ancien)
        ordre.append(s)
        for voisin in graphe[s]:
            if voisin not in visites:
                visites.add(voisin)     # (marque AVANT d'enfiler)
                file.append(voisin)
    return ordre

Déroulé pas à pas

Sur le graphe A: B,C — B: A,D — C: A,E — D: B — E: C, départ en A :

  file        visites          action
  [A]         {A}              sortir A, enfiler B, C
  [B, C]      {A,B,C}          sortir B, enfiler D
  [C, D]      {A,B,C,D}        sortir C, enfiler E
  [D, E]      {A,B,C,D,E}      sortir D (D->B déjà vu)
  [E]         {A,B,C,D,E}      sortir E (E->C déjà vu)
  []          -                file vide : fini

  ordre visite :  A  B  C  D  E

La propriété qui rend le BFS précieux

Dans un graphe non pondéré, le BFS trouve le plus court chemin (en nombre d'arêtes) du départ vers chaque sommet. Puisqu'il explore vague par vague, un sommet atteint à la vague k est forcément à k arêtes du départ — impossible de faire plus court. C'est ce qui sert, par exemple, à trouver le « degré de séparation » entre deux personnes d'un réseau social.

En résumé

Le BFS explore un graphe par vagues successives à l'aide d'une file et d'un ensemble de sommets visités (indispensable à cause des cycles). Il visite les sommets par distance croissante au départ, ce qui lui permet de trouver le plus court chemin en nombre d'arêtes.