DFS, récursion et piles itératives
Explorer en profondeur et éviter les limites de récursion
DFS, récursion et piles itératives est une leçon Competitive Programming Academy gratuite sur CoddyKit. Ceci est la leçon 3 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Competitive Programming Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Competitive Programming Academy comprend 4 leçons au total.
Ce que fait DFS
DFS descend aussi profondément que possible le long d’un chemin, puis revient en arrière et essaie le suivant. Imaginez que vous explorez un labyrinthe couloir après couloir. 🧭
DFS contre BFS
BFS s’étend par couches, tandis que DFS va d’abord au plus profond. Les deux visitent chaque nœud accessible, mais dans un ordre très différent.
La structure récursive
Un DFS récursif marque un nœud comme visité, puis s’appelle lui-même pour chaque voisin non visité. La pile d’appels mémorise l’endroit où reprendre l’exécution.
def dfs(u):
visited[u] = True
for v in adj[u]:
if not visited[v]:
dfs(v)Marquer avant l’appel récursif
Définissez visited en entrant dans un nœud, avant d’explorer ses voisins. Sinon, les cycles font entrer DFS dans une récursion infinie.
Le piège de la limite de récursion
Python limite la récursion à environ 1 000 appels. Un graphe profond déclenche une RecursionError, qui apparaît comme une erreur d’exécution dans le résultat.
Augmenter la limite
Une solution rapide consiste à relever la limite avec setrecursionlimit. Définissez-la au-dessus de la profondeur maximale possible avant d’exécuter DFS.
import sys
sys.setrecursionlimit(300000)Préférer une version itérative
La solution la plus sûre consiste à utiliser un DFS itératif avec votre propre pile. Sans profondeur d’appel, vous n’aurez jamais de plantage dû à la récursion.
stack = [start]Retirer un élément de la pile
À chaque étape, utilisez pop sur le sommet de la pile. Le principe « dernier entré, premier sorti » permet à DFS de suivre d’abord le chemin le plus récemment découvert.
u = stack.pop()Empiler les voisins
Après avoir retiré u, empilez chaque voisin non visité. Marquez-les afin de ne pas les empiler à nouveau.
for v in adj[u]:
if not visited[v]:
visited[v] = True
stack.append(v)La boucle itérative complète
Répétez pop et l’empilement tant que la pile contient des nœuds. Lorsqu’elle est vide, chaque nœud accessible a été visité.
while stack:
u = stack.pop()
for v in adj[u]:
if not visited[v]:
visited[v] = True
stack.append(v)Le même coût que BFS
Comme BFS, DFS visite chaque nœud et chaque arête une fois, avec une complexité en O(n + m). Choisissez selon l’ordre adapté à la tâche.
Vérification rapide
Votre DFS récursif plante sur un graphe profond. Pourquoi ?
Récapitulatif
Vous exécutez DFS récursivement ou avec votre propre pile, vous marquez les nœuds comme visités dès leur entrée et vous passez à la version itérative lorsque le graphe devient profond. 🎉
Questions Fréquemment Posées
La leçon « DFS, récursion et piles itératives » est-elle gratuite ?
Oui — le texte complet de « DFS, récursion et piles itératives » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Competitive Programming Academy, passe à CoddyKit PRO. Le cours Competitive Programming Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « DFS, récursion et piles itératives » ?
Explorer en profondeur et éviter les limites de récursion Tu pratiques Competitive Programming Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Competitive Programming Academy ?
Aucune expérience préalable n'est requise. Competitive Programming Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 3 sur 4.
Combien de temps prend la leçon « DFS, récursion et piles itératives » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Competitive Programming Academy ?
Oui. Chaque leçon Competitive Programming Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Listes d’adjacence à partir de l’entrée
- BFS pour les plus courts chemins non pondérés
- DFS, récursion et piles itératives
- Composantes connexes et remplissage par diffusion