Motivation
Leçon 2 sur 9 du cours Parcours en largeur - Algorithmes de graphes de Coddy.
Le BFS utilise une file (premier entré, premier sorti) afin que les sommets soient traités dans l'ordre exact où ils ont été découverts, ce qui produit une exploration par couches.
Pourquoi apprendre le BFS ?
- Plus courts chemins : dans un graphe non pondéré, le BFS trouve le chemin avec le moins d'arêtes entre le point de départ et tous les autres sommets.
- Simple et linéaire : il s'exécute en O(V + E) avec une file et un marqueur de visite.
- Partout : les sauts les plus courts dans les réseaux, les échelles de mots, la résolution de labyrinthes et le parcours d'arbre par niveaux sont tous basés sur le BFS.
Comme pour le DFS, nous enfilons les voisins d'un sommet par ordre croissant afin que les résultats soient prévisibles.
Essayez vous-même
Cette leçon ne comprend pas de défi de code.
Testez-vousCette leçon comprend un petit quiz. Commencez la leçon pour y répondre et suivre votre progression.
