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.
- temps O(V + E)
- espace O(V)
- utilise une file
Que veulent dire ces termes ?
- 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.
- File : premier entré, premier sorti. BFS prend toujours le sommet qui attend depuis le plus longtemps.
- Pile : dernier entré, premier sorti. DFS repart toujours du dernier sommet atteint.
- 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.
- dans la file
- en cours
- traité
- arête de l'arbre de parcours
- arête ignorée
Départ de A. Appuyez sur Lire ou avancez pas à pas.
Espace : lecture ou pause. Flèches gauche et droite : pas à pas. Origine et Fin : sauter.
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.