Parcours en largeur (BFS)
Explore un graphe couche par couche. Une file décide du sommet suivant, donc les sommets les plus proches sont toujours visités en premier.
- O(V + E)
- espace O(V)
- file
V et E : le nombre de sommets et d'arêtes. O(V + E) veut dire que chaque sommet et chaque arête sont traités un nombre fixe de fois.
File : premier entré, premier sorti. BFS prend toujours le sommet qui attend depuis le plus longtemps.
Autres termes de cette page
- Sommet : un point du graphe, dessiné ici comme un cercle avec une lettre.
- Arête : une ligne qui relie deux sommets. Ici, on peut la parcourir dans les deux sens.
- Voisins : les sommets reliés à un sommet par une arête. On les examine dans l'ordre alphabétique.
Essayez : Choisissez le graphe en deux parties. Les sommets qui ne sont pas reliés au départ ne sont jamais atteints.
Comment ça marche
BFS met le sommet de départ dans une file. Puis, encore et encore, il prend le sommet en tête de file et ajoute ses nouveaux voisins au bout. Une file sert dans l'ordre d'arrivée : tous les sommets à une arête du départ sont donc traités avant ceux à deux arêtes. Le nombre à côté d'un sommet est sa distance au départ : le plus petit nombre d'arêtes pour l'atteindre.
Quand le choisir
Utilisez BFS quand il faut le chemin le plus court en nombre d'étapes : le moins de coups dans un casse-tête, le moins de sauts dans un réseau, les personnes à deux relations de vous. Sur un grand graphe, la file peut devenir longue, car elle contient toute une couche à la fois.