Algorithme de parcours en largeur

Un article de Wikipédia, l'encyclopédie libre.

Pour les articles homonymes, voir BFS.

L'algorithme de parcours en largeur (ou BFS, pour Breadth First Search) permet le parcours d'un graphe de manière itérative, en utilisant une file. Il peut par exemple servir à déterminer la connexité d'un graphe.

[modifier] Principe

Cet algorithme diffère de l'algorithme de parcours en profondeur par le fait que, à partir d'un sommet S, il liste d'abord les voisins de S pour ensuite les explorer un par un. Ce mode de fonctionnement utilise donc une file FIFO dans laquelle il prend le premier sommet et place en dernier ses voisins non encore explorés.

Si le graphe est cyclique, il faudra en outre marquer les sommets déjà visités pour que l'algorithme puisse se terminer.

1. Mettre le nœud de départ dans la file.
2. Retirer le nœud du début de la file pour l'examiner.
3. Mettre tous les voisins non examinés dans la file (à la fin).
4. Si la file n'est pas vide reprendre à l'étape 2.

[modifier] Implémentation

BFS(graphe G, sommet s):
{
  f= CreerFile();
  Marquer(s);
  Enfiler(f, s);
  TANT-QUE NON FileVide(f) FAIRE
      x = Défiler(f);
      Afficher(x)
      TANT-QUE ExisteFils(x) FAIRE
          z = FilsSuivant(x);
          SI NonMarqué(z) ALORS 
              Marquer(z);
              Enfiler(f, z);
          FIN-SI
      FIN-TANT-QUE
  FIN-TANT-QUE
}

[modifier] Exemple

Sur le graphe suivant, cet algorithme va alors fonctionner ainsi:

Il explore dans l'ordre les sommets A, B, C, E, D, F, G, contrairement à l'algorithme de parcours en profondeur qui cherche dans cet ordre : A, B, D, F, E, C, G.