Algorithme de parcours en largeur

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie 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.

Exemple animé de l'algorithme de parcours en largeur.

Principe[modifier | modifier le code]

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 dans laquelle il prend le premier sommet et place en dernier ses voisins non encore explorés.

Lorsque l'algorithme est appliqué à un graphe quelconque, les sommets déjà visités doivent être marqués afin d'éviter qu'un même sommet soit exploré plusieurs fois. Dans le cas particulier d'un arbre, ce n'est pas nécessaire.

Étapes de l'algorithme :

  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.

Note : l'utilisation d'une pile au lieu d'une file d'attente transformerait cet algorithme en un algorithme de parcours en profondeur.

Exemple[modifier | modifier le code]

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

Graphes.dfs-bfs.exemple.png

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, C, G, E.

Pseudo code[modifier | modifier le code]

ParcoursLargeur(Sommet s):
{
  f = CreerFile();
  f.enfiler(s);
  marquer(s);
  TANT-QUE NON f.vide() FAIRE
      s = f.defiler();
      afficher(s);    
      POUR TOUT voisin de s FAIRE
           SI voisin non marqué FAIRE
                f.enfiler(voisin);
                marquer(voisin);
           FIN SI
      FIN POUR TOUT 
  FIN TANT QUE       
 }

Complexité[modifier | modifier le code]

La complexité en temps dans le pire cas est de l'ordre de E+V puisque chaque arête et chaque sommet peuvent être visités.

Analyse par agrégat[Quoi ?] :

Soit un graphe G=(V,E), avec à l'appel de l'algorithme aucun sommet n'est marqué. Tous les sommets insérés dans la file sont marqués et l'instruction conditionnelle assure donc que les sommets seront insérés au plus une fois, comme l'insertion dans la file se fait en Θ(1), la compléxité est en Θ(V). Les voisins étant donnés par liste d'adjacence seront visités au plus E fois car la somme des longueurs des listes d'adjacence est E (le nombre d'arêtes). La compléxité totale est donc Θ(V+E). [1]

Applications[modifier | modifier le code]

Le parcours en largeur explore tous les sommets accessibles depuis le sommet initial. Il permet de calculer les composantes connexes du graphe avec une complexité linéaire.

De plus, lors de ce parcours, les sommets sont explorés par distance croissante au sommet de départ. Grâce à cette propriété, on peut utiliser l'algorithme pour résoudre le plus simple des problèmes de cheminement : calculer le plus court chemin entre deux sommets dans un graphe non pondéré.

Notes et références[modifier | modifier le code]

  1. Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein, "Introduction à l'algorithmique", DUNOD, 2001, 3e éd. (1re éd. 1990), 1176 p. (ISBN 2-10-003922-9)

Voir aussi[modifier | modifier le code]