Parcours en Profondeur (DFS)
Algorithmique classique
Enonce
Effectuer un parcours en profondeur (DFS) 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 dfs(graphe: dict, depart: int) -> list:Exemples
dfs({0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}, 0)→[0, 1, 3, 2]dfs({0: [1, 2], 1: [3], 2: [3], 3: []}, 0)→[0, 1, 3, 2]
📖 Rappel de cours
On explore aussi loin que possible avant de revenir en arrière. Une pile, ou la récursion qui en tient lieu, et un ensemble des sommets déjà visités.
⚠ Le piège : Sans marquage des visités, un cycle fait tourner l'algorithme indéfiniment. Le DFS ne donne pas le plus court chemin, contrairement au parcours en largeur.
← Exercices Python pour la prépa — CPGE scientifique et ECG
Exercices du meme theme
- Recherche dans un ABR
- Arbre Binaire Miroir
- Matrice d'Adjacence → Liste d'Adjacence
- Parcours en Largeur (BFS)
- Degré des Sommets
- Composantes Connexes
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.