Numérique et sciences informatiques (spécialité) · Terminale · Algorithmique
Parcours de graphes en largeur et en profondeur
- Un parcours visite les sommets d'un graphe à partir d'une source, chacun une seule fois grâce au marquage des sommets déjà vus.
- Le parcours en largeur (BFS) utilise une file : il explore la source, puis ses voisins, puis les voisins de ses voisins.
- Le parcours en profondeur (DFS) s'enfonce dans un chemin jusqu'à un cul-de-sac, puis revient en arrière ; il s'écrit naturellement en récursif, ou avec une pile.
- Le BFS donne les distances depuis la source dans un graphe non pondéré ; les deux parcours donnent les sommets accessibles et les composantes connexes.