Parcours en largeur (breadth-first search)

Répertoire GitHub correspondant à cet article : https://github.com/peportier/ia02-bfs

Structure FIFO

En utilisant pour (la structure qui contient les nœuds rencontrés mais dont les successeurs n'ont pas encore été calculés, c'est-à-dire les nœuds gris) une structure de file FIFO (First In First Out) au lieu d'un ensemble, nous obtenons le programme de recherche en largeur dans un graphe.

Nous suivons le schéma de l'algorithme générique dérivé précédemment. Pour ne pas avoir à chercher la présence d'un nœud dans la file y afin de savoir s'il est gris, l'ensemble x contient les nœuds gris et les nœuds noirs.

Nous utilisons un visiteur trivial :

largeur

Calcul des plus courts chemins

L'algorithme de recherche en largeur permet de trouver les plus courts chemins d'un nœud source aux autres nœuds du graphe dans le cas d'un graphe orienté pour lequel les arêtes ont toutes le même coût (ou poids) :

Le programme principal calcule les plus courtes distances au noeud source 1 sur notre exemple filé.

Nous trouvons bien :

largeur-plus-courts-chemins