BFS — explication de l’algorithme de parcours en largeur

Le parcours en largeur, ou BFS, est un algorithme de graphe qui visite les nœuds selon leur distance à partir d’un nœud de départ. Il examine tous les nœuds situés à une arête avant de passer à ceux situés à deux arêtes, puis à trois arêtes, et ainsi de suite.

Cet ordre par couches est l’idée essentielle. Si le graphe est non pondéré, ou si chaque arête a le même coût, BFS donne aussi la longueur du plus court chemin entre le nœud de départ et chaque nœud atteignable.

Ce que fait le parcours en largeur

BFS utilise une file, c’est-à-dire une liste premier entré, premier sorti. C’est la file qui conserve l’ordre par couches : les nœuds découverts plus tôt sont traités plus tôt.

Le schéma habituel est le suivant :

• marquer le nœud de départ comme visité
• le placer dans la file
• retirer le nœud en tête de file
• ajouter chaque voisin non visité à la fin de la file
• répéter jusqu’à ce que la file soit vide

Si vous stockez aussi le parent de chaque nœud, vous pouvez reconstruire un plus court chemin une fois la recherche terminée.

Pourquoi la file crée des couches

Supposons que le nœud $A$ soit le point de départ. Ses voisins directs sont à une distance $1$ de $A$, donc ils entrent d’abord dans la file. Ce n’est qu’après le traitement de ces nœuds que leurs voisins non visités y entrent à leur tour, ce qui signifie que la vague suivante est à distance $2$.

C’est pour cela que BFS regroupe naturellement les nœuds selon leur distance au départ. Il n’essaie pas d’estimer quel chemin est court. La file force la recherche à terminer tous les chemins avec moins d’arêtes avant d’examiner les plus longs.

Exemple de BFS : trouver le plus court chemin en nombre d’arêtes

Utilisez ce graphe :

$$A \to \{B, C\}, \qquad B \to \{D\}, \qquad C \to \{E\}, \qquad D \to \{F\}, \qquad E \to \{F\}$$

Commencez en $A$. La file évolue ainsi :

$$[A] \to [B, C] \to [C, D] \to [D, E] \to [E, F] \to [F]$$

Voici ce que cela signifie :

D’abord, on traite $A$, puis on ajoute $B$ et $C$. Ensuite, on traite $B$ puis $C$, ce qui ajoute $D$ et $E$. Après cela, on traite $D$ et $E$, ce qui permet d’atteindre $F$.

L’ordre de visite de BFS est donc :

$$A,\ B,\ C,\ D,\ E,\ F$$

Les distances à partir de $A$ sont :

$$\operatorname{dist}(A)=0,\quad \operatorname{dist}(B)=1,\quad \operatorname{dist}(C)=1,\quad \operatorname{dist}(D)=2,\quad \operatorname{dist}(E)=2,\quad \operatorname{dist}(F)=3$$

Cela montre l’intérêt principal. BFS atteint $F$ à la distance $3$, donc le plus court chemin de $A$ à $F$ utilise $3$ arêtes. Un plus court chemin est $A \to B \to D \to F$. Un autre est $A \to C \to E \to F$.

Erreurs fréquentes avec BFS

Penser que BFS trouve toujours le chemin le moins coûteux

C’est vrai seulement lorsque toutes les arêtes ont le même coût, ou lorsque le graphe est considéré comme non pondéré. Si les arêtes ont des poids différents, BFS peut trouver un chemin avec moins d’arêtes mais un coût total plus élevé.

Marquer un nœud trop tard

Dans un BFS standard, un nœud est généralement marqué comme visité au moment où il est ajouté à la file, et non plus tard lorsqu’il en est retiré. Cela évite d’ajouter plusieurs fois le même nœud dans la file.

Confondre BFS et DFS

BFS explore par couches. Le parcours en profondeur, ou DFS, suit une branche aussi loin que possible avant de revenir en arrière. Ces deux algorithmes répondent bien à des types de questions différents.

Oublier que l’ordre peut dépendre de l’ordre des voisins

L’ordre exact de visite à l’intérieur d’une même couche peut changer selon la manière dont les voisins sont listés. Les garanties sur les distances restent valables, mais l’ordre de parcours peut varier.

Quand le parcours en largeur est utilisé

BFS est utile lorsqu’on s’intéresse à l’accessibilité, au parcours par niveaux dans les arbres, ou aux longueurs des plus courts chemins mesurées en nombre d’arêtes.

On le retrouve aussi dans des problèmes d’espace d’états où chaque déplacement a le même coût. Dans cette situation, BFS est souvent la façon la plus claire de trouver le nombre minimal de déplacements.

Une façon simple de retenir BFS

Imaginez BFS comme une onde qui se propage vers l’extérieur à partir du nœud de départ. Chaque nouvelle onde ajoute une arête supplémentaire de distance.

Pour essayer vous-même, dessinez un petit graphe, choisissez un nœud de départ et notez l’état de la file après chaque étape. Si vous voulez aller plus loin, résolvez un problème similaire de parcours de graphe et vérifiez si l’affirmation sur le plus court chemin reste vraie lorsque le graphe est pondéré.