Exercices de programmation pour classes préparatoires
Écrire une fonction bfs : int list array -> int -> int list qui effectue un parcours en largeur (BFS) d'un graphe à partir d'un sommet de départ, et renvoie la liste des sommets visités dans l'ordre de visite.
Représentation : le graphe est un tableau adj de type int list array (liste d'adjacence). Les sommets sont numérotés de 0 à n-1.
Quand plusieurs voisins sont possibles, on les visite dans l'ordre croissant des numéros de sommets. On utilisera le module Queue de la bibliothèque standard pour implémenter la file.
| Appel | Résultat attendu |
|---|---|
| bfs [| [1; 2]; [0]; [0] |] 0 | [0; 1; 2] |
| bfs [| [1; 2]; [0; 3]; [0]; [1] |] 0 | [0; 1; 2; 3] |
Connectez-vous pour soumettre du code.