Parcours en profondeur : DFS en Terminale
Parcours en profondeur : DFS, c'est une notion de nsi du chapitre « Algorithmique avancée », au programme de Terminale. Voici le cours, un exemple et de quoi t'entraîner.
Parcours en profondeur : DFS : le cours
Le parcours en profondeur explore un graphe en allant aussi loin que possible dans une branche avant de revenir en arrière. Il utilise une pile (récursion ou structure).
Exemple
Explorer un labyrinthe : tu avances le plus loin possible dans un couloir, puis tu reviens en arrière pour essayer un autre chemin.
À retenir
DFS est utile pour détecter les cycles, trouver les composantes connexes et explorer tous les chemins possibles.
S'entraîner sur parcours en profondeur : dfs
Fais l'exercice, puis demande au tuteur de te corriger pas à pas.
Exercice 1
Écris une fonction récursive avec mémoïsation pour calculer le nombre de façons de monter un escalier de n marches si tu peux monter 1 ou 2 marches à la fois. Quelle est la complexité sans et avec mémoïsation ?
Corrige cet exercice avec le tuteur →Exercice 2
Implémente un BFS pour trouver le chemin le plus court entre deux nœuds dans un graphe représenté par une liste d'adjacence. Pourquoi BFS et pas DFS ?
Corrige cet exercice avec le tuteur →Cette notion fait partie du chapitre Algorithmique avancée (NSI Terminale).