Graphe par Dictionnaire — BFS
Dictionnaires
Enonce
Écrire une fonction qui effectue un parcours en largeur (BFS) d'un graphe représenté par dictionnaire d'adjacence, depuis un sommet depart. Renvoyer la liste des sommets visités dans l'ordre du parcours.
g = {'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A', 'D'], 'D': ['B', 'C']}
parcours_largeur(g, 'A') → ['A', 'B', 'C', 'D']Signature attendue
def parcours_largeur(graphe: dict, depart) -> list:Exemple
parcours_largeur({1: [2, 3], 2: [1, 4, 5], 3: [1], 4: [2], 5: [2]}, 1)→[1, 2, 3, 4, 5]
Graphe par dictionnaire d'adjacence
Un graphe peut être représenté par un dictionnaire où chaque clé est un sommet et la valeur associée est la liste de ses voisins. Le parcours en largeur (BFS) explore les sommets couche par couche en utilisant une file (ici une liste avec pop(0)). C'est un classique absolu de CPGE.
← Exercices Python pour la prépa — CPGE scientifique et ECG
Exercices du meme theme
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.