Introduction

Bienvenue dans la suite de la série sur les Algorithmes de Graphes ! Après le parcours en profondeur (DFS), nous passons au parcours en largeur (BFS), l'autre parcours de graphe fondamental.

Là où le DFS plonge en profondeur, le BFS explore par couches : d'abord le sommet de départ, puis tous ses voisins, puis tout ce qui se trouve à deux pas, et ainsi de suite. Cet ordre couche par couche est précisément ce qui permet au BFS de trouver les plus courts chemins dans les graphes non pondérés.

Comme dans le reste de la série, un graphe est donné sous la forme de n (nombre de sommets, de 0 à n - 1) et edges, un tableau plat de paires non orientées [u0, v0, u1, v1, ...].

Commençons !