Exercices de programmation pour classes préparatoires
Ecrire une fonction bfs(graphe, depart) qui effectue un parcours en largeur (BFS) d'un graphe a partir d'un sommet de depart, et renvoie la liste des sommets visites dans l'ordre de visite.
Representation : le graphe est represente par un dictionnaire d'adjacence {sommet: [voisins]}. Par exemple {'A': ['B', 'C'], 'B': ['A'], 'C': ['A']} represente un graphe non oriente ou A est relie a B et C.
Quand plusieurs voisins sont possibles, choisissez-les dans l'ordre alphabetique (ou numerique). Utilisez une file (par exemple collections.deque) pour implementer le BFS.
| Appel | Résultat attendu |
|---|---|
| bfs({'A': ['B', 'C'], 'B': ['A'], 'C': ['A']}, 'A') | ['A', 'B', 'C'] |
| bfs({'A': ['B'], 'B': ['A']}, 'A') | ['A', 'B'] |
| bfs({'A': []}, 'A') | ['A'] |
Connectez-vous pour soumettre du code.