Laboratoire Python Interactif

Depth-First Search

Le playground s'exécute automatiquement au chargement. Cliquez sur Exécuter mon code pour tracer votre propre Python — chaque étape animée en direct.

Expliquer·Ligne par ligne

Rejouer·Étape par étape

Défi·Indices guidés

XP·...

Pipeline de Flux de Données

advanced Parcours

Bubble Sort

Two Sum

Valid Parentheses

Merge Sort

Quick Sort

Heap Sort

Breadth-First Search

Depth-First Search

Binary Tree Traversal

Fibonacci (Recursive)

Expliquer

Line 10

graph = {0:[1,2], 1:[0,3], 2:[0], 3:[1]}. Start DFS from node 0.

Pourquoi cette approche ?

Undirected graph with 4 nodes and 3 edges (0-1, 0-2, 1-3). Represented as adjacency list with each edge appearing twice (both directions). DFS will visit all 4 nodes starting from 0.

Structured Explanation

Overview

La recherche en profondeur d'abord (DFS) explore aussi loin que possible le long de chaque branche avant de revenir en arrière.

Analogy

Comme explorer un labyrinthe en allant toujours tout droit jusqu'à un cul-de-sac, puis en revenant sur tes pas.

Step-by-step

Commence depuis le nœud source, marque-le visité
Visite un voisin non visité
Continue récursivement jusqu'à ce qu'il n'y en ait plus
Reviens en arrière et essaie d'autres branches

Visual

Graphe: A-B, A-C, B-D DFS depuis A: A → B → D → C Pile: [A] → [B,C] → [C,D] → [C]

Common mistakes

Oublier de marquer les nœuds visités dans les graphes cycliques
Confusion entre récursif et itératif (pile explicite)

Practice questions

Détecte les cycles dans un graphe
Trouve tous les chemins entre deux nœuds

Time

O(V + E)

Space

O(V)

Complexité

Temps

O(V + E)

Espace

O(V)

Aperçu de la Complexité

O(1)

O(log n)

O(n)temps

O(n log n)

O(n²)

n = 8plage 1-20

POUR N = 8

Complexité	Opérations
O(1)	1
O(log n)	3
O(n)	8
O(n log n)	24
O(n²)	64

Défi

Parcours en profondeur (DFS)

Indice

Explore le graphe en profondeur avec une pile ou récursion.

Studio de Code

Depth-First Search

Monaco Prêt

Python Prêt

lesson.pyline 10

Loading editor...

Console de Sortie

0 lines

Pas encore de sortie...

Chronologie

Structures de Données

Pile d'appels (Primitives & Références)

graphobj

VALEUR PILE

{0:[1,2], 1:[0,3], 2:[0], 3:[1]}

Applications du Monde Réel

1

Résolution de labyrinthes et recherche de chemin

2

Tri topologique et détection de cycles

3

Composantes fortement connexes

Comments

Loading comments...