Parcours en largeur (BFS)

Lancez une pierre dans une mare et les ondes s'étendent en anneaux réguliers. Le parcours en largeur explore un graphe de la même façon : d'abord tout ce qui est à un pas du départ, puis tout ce qui est à deux pas, et ainsi de suite. C'est cet ordre simple qui lui fait trouver les plus courts chemins.

Un graphe de nœuds marqués de lettres, colorés en anneaux selon leur distance au nœud de départ, avec une file de nœuds dessinée en dessous
Un graphe de nœuds marqués de lettres, colorés en anneaux selon leur distance au nœud de départ, avec une file de nœuds dessinée en dessous

L'idée

Un graphe est un ensemble de nœuds reliés par des arêtes : des lieux et des routes, des personnes et des amitiés, les cases d'un labyrinthe et les passages entre elles. Le parcours en largeur répond à la question : en partant d'ici, que puis-je atteindre, et en combien de pas au minimum ? Il garde une file des nœuds encore à visiter. Comme on prend les nœuds en tête et qu'on ajoute les nouveaux en fin de file, les nœuds sont traités dans l'ordre où ils ont été découverts.

Pas à pas

Placez le départ dans la file à distance 0. Prenez le nœud en tête. Pour chaque voisin pas encore vu, notez sa distance, égale à celle du nœud courant plus un, retenez le nœud courant comme celui par lequel il a été atteint, et ajoutez-le en fin de file. Ignorez les voisins déjà vus. Recommencez jusqu'à ce que la file soit vide ou que la cible soit atteinte.

Un exemple

Prenez un graphe avec les arêtes A–B, A–C, B–D, C–D, C–E et D–F, et partez de A. Retirer A de la file trouve B et C à distance 1. Retirer B trouve D à distance 2. Retirer C montre que D a déjà été vu, et trouve E à distance 2. Retirer D trouve F à distance 3. E et F ne trouvent rien de nouveau, et la file est vide. Remonter les nœuds retenus depuis F donne F ← D ← B ← A, donc un plus court chemin de A à F est A → B → D → F, long de trois arêtes.

Pourquoi les distances sont justes

Chaque nœud à distance 1 entre dans la file avant tout nœud à distance 2, chaque nœud à distance 2 avant tout nœud à distance 3, et ainsi de suite, car les voisins d'un nœud n'entrent dans la file que lorsque ce nœud en sort. Le premier chemin qui atteint un nœud a donc le moins d'arêtes, et BFS n'a jamais besoin de corriger une distance. Chaque nœud est pris une fois et chaque arête examinée depuis ses deux extrémités, donc le travail croît avec le nombre de nœuds plus le nombre d'arêtes.

Histoire et usages

Konrad Zuse a décrit le parcours en largeur en 1945, dans des travaux sur son langage Plankalkül publiés seulement en 1972. Edward F. Moore l'a réinventé en 1959 pour trouver le plus court chemin pour sortir d'un labyrinthe, et C. Y. Lee l'a utilisé en 1961 pour router les pistes des circuits imprimés. Aujourd'hui, il trouve le moins de coups dans les casse-tête, les degrés de séparation dans les réseaux sociaux, les pages qu'un robot d'indexation atteint en premier et la case libre la plus proche dans les jeux. Quand les arêtes ont des longueurs, l'algorithme de Dijkstra le généralise.

Konrad Zuse (au centre, avec des lunettes) et Heinz Billing (à gauche) au salon SYSTEMS ’91 à Munich. Zuse décrivit la recherche en largeur en 1945, dans des travaux sur son langage Plankalkül qui ne furent publiés qu’en 1972.
Konrad Zuse (au centre, avec des lunettes) et Heinz Billing (à gauche) au salon SYSTEMS ’91 à Munich. Zuse décrivit la recherche en largeur en 1945, dans des travaux sur son langage Plankalkül qui ne furent publiés qu’en 1972.

À vous d'explorer

Ouvrez l'application et appuyez sur Étape. Le nœud visité est mis en évidence, les nœuds en attente dans la file sont bleus et les nœuds visités sont verts, chacun avec sa distance. La file est affichée sous le graphe, tête en premier. Basculez le clic sur Cible et choisissez un nœud pour vous y arrêter et voir le plus court chemin, ou créez un nouveau graphe avec plus de nœuds et d'arêtes.

Questions fréquemment posées

Quelle est la complexité en temps du BFS ?

O(V + E) pour V nœuds (sommets) et E arêtes : chaque nœud entre dans la file et en sort une fois, et chaque arête est examinée depuis ses deux extrémités. Il faut O(V) de mémoire en plus pour la file et les distances.

Pourquoi le BFS utilise-t-il une file ?

Parce que « premier entré, premier sorti » garde les nœuds dans l'ordre de leur découverte, qui est l'ordre de leur distance. Avec une pile à la place, la recherche plongerait d'abord en profondeur : c'est le parcours en profondeur.

Le BFS trouve-t-il les plus courts chemins dans un graphe pondéré ?

Pas en général : il compte les arêtes, pas leurs longueurs. Pour les graphes pondérés sans arêtes négatives, utilisez l'algorithme de Dijkstra. Si chaque poids vaut 0 ou 1, une variante appelée BFS 0-1 fonctionne.

Où utilise-t-on le BFS ?

Pour résoudre des casse-tête et des labyrinthes en un minimum de coups, trouver les amis d'amis dans les réseaux sociaux, explorer le web niveau par niveau, diffuser des messages dans les réseaux, et comme brique d'autres algorithmes, par exemple pour trouver des flots maximaux.

Prêt à l'essayer ?

Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

Essayer le parcours en largeur