Parcours en largeur BFS, Breadth-First Search
Parcours de graphe qui visite tous les nœuds d'une profondeur avant de passer à la suivante. S'implémente avec une file FIFO.
Il garantit le plus court chemin dans un graphe non pondéré. Usages classiques : nombre minimal de sauts entre deux nœuds (les « trois degrés » de LinkedIn), crawling du web, parcours d'arbre par niveaux, IA de jeu du type « gagner en un minimum de coups ».
Complexité en temps O(V+E), en espace O(V) dans le pire cas. Concurrents : DFS (une pile au lieu d'une file, on plonge d'abord en profondeur) et Dijkstra (quand les arêtes ont un poids).