Parcours en Largeur (BFS)
Algorithmique classique
Enonce
Effectuer un parcours en largeur (BFS) d'un graphe représenté par un dictionnaire de listes d'adjacence. Retourner la liste des sommets visités dans l'ordre.
Signature attendue
def bfs(graphe: dict, depart: int) -> list:Exemples
bfs({0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}, 0)→[0, 1, 2, 3]bfs({0: [1, 2], 1: [3], 2: [], 3: []}, 0)→[0, 1, 2, 3]
📖 Rappel de cours
On explore niveau par niveau à l'aide d'une file. Sur un graphe non pondéré, le premier chemin trouvé vers un sommet est le plus court en nombre d'arêtes.
⚠ Le piège : Marquer un sommet à l'enfilement, jamais au défilement : sinon il entre plusieurs fois dans la file et la complexité s'effondre. C'est une ligne, et elle départage les copies.
← Exercices Python pour la prépa — CPGE scientifique et ECG
Exercices du meme theme
- Arbre Binaire Miroir
- Matrice d'Adjacence → Liste d'Adjacence
- Parcours en Profondeur (DFS)
- Degré des Sommets
- Composantes Connexes
- Rendu de Monnaie Glouton
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.