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 en anglais) permet le parcours d'un graphe de la manière suivante : on commence par explorer un noeud source, puis ses successeurs, puis les successeurs non explorés des successeurs, etc. L'algorithme de parcours en largeur permet de calculer les distances de tous les nœuds depuis un nœud source dans un graphe non pondéré (orienté ou non orienté). Il peut aussi servir à déterminer si un graphe non orienté est connexe.

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 nœud source 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.

Les nœuds déjà visités sont marqués afin d'éviter qu'un même nœud soit exploré plusieurs fois. Dans le cas particulier d'un arbre, le marquage n'est pas nécessaire.

Étapes de l'algorithme :

  1. Mettre le nœud source dans la file.
  2. Retirer le nœud du début de la file pour l'examiner.
  3. Mettre tous les voisins non exploré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 transforme l'algorithme du parcours en largeur en l'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]

L'algorithme s'implémente à l'aide d'une file.

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

Complexité[modifier | modifier le code]

La complexité en temps dans le pire cas est en O(|S| + |A|)|S| est le nombre de sommets et |A| est le nombre d'arcs. En effet, chaque arc et chaque sommet est visité au plus une seule fois.

Analyse par agrégat[Quoi ?] :

Soit un graphe G=(V,E), dont aucun sommet n'est marqué à l'appel de l'algorithme. 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 complexité 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 complexité totale est donc Θ(V+E). [1]

Applications[modifier | modifier le code]

Le parcours en largeur explore tous les sommets accessibles depuis le sommet source. On peut utiliser cet algorithme pour calculer les composantes connexes d'un graphe non orienté avec une complexité linéaire en la taille du graphe.

De plus, lors de ce parcours, les sommets sont explorés par distance croissante au sommet source. Grâce à cette propriété, on peut utiliser l'algorithme pour résoudre le problème de cheminement suivant : calculer des plus courts chemins entre le sommet source et tous les sommets du graphe.

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]