- Breadth First Search
-
Algorithme de parcours en largeur
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.
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.
- Mettre le nœud de départ dans la file.
- Retirer le nœud du début de la file pour l'examiner.
- Mettre tous les voisins non examinés dans la file (à la fin).
- Si la file n'est pas vide reprendre à l'étape 2.
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 }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, C, G, E.
Catégories : Algorithme de recherche | Arbre (structure de données) | Algorithme de la théorie des graphes
Wikimedia Foundation. 2010.
