Visualiseur DFS en Ligne

Pseudocode

DFS s'écrit généralement de façon récursive, mais la forme itérative rend la pile explicite et évite de saturer la pile d'appels sur les graphes profonds. Les deux produisent le même ordre de découverte.

DFS(graphe, source):
    temps = 0
    visiter(source)

visiter(u):
    visites.ajouter(u)
    dec[u] = ++temps            // date de découverte
    pour chaque voisin v de u:
        si v absent de visites:
            parent[v] = u
            visiter(v)
    fin[u] = ++temps            // date de fin

Les dates de découverte et de fin sont le véritable produit du DFS. L'intervalle [dec[u], fin[u]] d'un descendant est strictement imbriqué dans celui de son ancêtre, et cette imbrication fonde le tri topologique, la détection de cycles, les composantes fortement connexes de Tarjan, les points d'articulation et les ponts.

Exemple détaillé, étape par étape

Exécute DFS depuis A sur le graphe chargé par défaut dans le visualiseur, en prenant toujours les voisins par ordre alphabétique.

Graphe d'exemple: Arêtes non orientées A-B (2), A-C (3), B-C (1) et C-D (4). DFS ignore les poids.

1. Visiter A. dec[A] = 1. Le premier voisin non visité est B, donc on descend immédiatement au lieu de regarder aussi C.
2. Visiter B. dec[B] = 2. Ses voisins sont A, qui est le parent et se saute, et C, non visité. On descend dans C.
3. Visiter C. dec[C] = 3. Ses voisins sont A, B et D. A est visité et n'est pas le parent, donc A-C est une arête arrière et prouve l'existence d'un cycle. B est le parent. D n'est pas visité, on descend donc dans D.
4. Visiter D. dec[D] = 4. Son unique voisin est C, le parent. Il n'y a plus rien à faire, donc fin[D] = 5.
5. Remonter. Le contrôle revient à C, qui n'a plus de voisins, donc fin[C] = 6. Puis B termine à 7, et A, dont le voisin restant C est désormais visité, termine à 8.

L'ordre de parcours est A, B, C, D. BFS visite ces quatre sommets dans le même ordre, mais les arbres diffèrent: BFS construit un arbre plat avec A vers B, A vers C et C vers D, tandis que DFS construit la chaîne unique A vers B vers C vers D. L'arête arrière C vers A identifie le cycle A-B-C-A, et les intervalles imbriqués A[1,8], B[2,7], C[3,6], D[4,5] montrent directement la profondeur de récursion.

Complexité et son origine

Temps: O(V + E) · Espace: O(V)

Chaque sommet est visité exactement une fois car le test de visite protège l'appel récursif, et chaque arête est examinée une fois depuis chaque extrémité, soit 2E inspections dans un graphe non orienté et E dans un graphe orienté. L'espace est l'ensemble des visités plus la pile de récursion, tous deux en O(V). La profondeur de récursion vaut la longueur du plus long chemin simple, donc sur un graphe en chaîne d'un million de sommets une implémentation récursive saturera la pile d'appels dans la plupart des langages et il faut la forme à pile explicite.

Quand utiliser Recherche en Profondeur (DFS), et quand l'éviter

Choisis DFS quand la question porte sur la structure. Choisis BFS quand elle porte sur la distance.

Pièges fréquents

• Débordement de pile sur les graphes profonds. Le DFS récursif s'appelle une fois par sommet le long d'un chemin. Autour de 10 000 à 100 000 sommets selon le langage, la pile d'appels meurt. Convertis en pile explicite, ou relève délibérément la limite de récursion si le langage le permet.
• Traiter l arête vers le parent comme une arête arrière. Dans un graphe non orienté, chaque arête apparaît des deux côtés, donc l'arête de retour vers le parent ressemble toujours à une arête arrière. Saute le parent explicitement, et souviens-toi qu'avec des arêtes parallèles il ne faut le sauter qu'une fois.
• Utiliser l ensemble des visités pour détecter un cycle orienté. Dans un graphe orienté, rencontrer un sommet visité n'implique pas un cycle. Ce peut être une arête transverse vers un sous-arbre déjà terminé. Il faut trois couleurs: non visité, dans la pile de récursion courante, et terminé. Seule une arête vers la pile de récursion ferme un cycle.
• Supposer que l ordre de parcours est unique. La sortie du DFS dépend de l'ordre d'itération des voisins. Deux implémentations correctes peuvent produire des ordres valides différents, raison pour laquelle les tests devraient vérifier des propriétés et non une séquence exacte.

Questions fréquentes

À quoi sert le parcours en profondeur?

DFS fonde le tri topologique, la détection de cycles, les composantes fortement connexes, les points d'articulation et les ponts, ainsi que la génération de labyrinthes. En production, il sous-tend la résolution de dépendances dans les outils de compilation et les gestionnaires de paquets, la détection d'interblocages et les solveurs par retour sur trace.

Quelle est la complexité temporelle du DFS?

O(V + E) en temps et O(V) en espace avec une liste d'adjacence. Chaque sommet est visité une fois et chaque arête inspectée une fois depuis chaque extrémité. L'espace comprend l'ensemble des visités et la pile de récursion, dont la profondeur vaut le plus long chemin simple du graphe.

Le DFS est-il récursif ou itératif?

L'un ou l'autre. La forme récursive est plus courte et fait apparaître naturellement les dates de découverte et de fin. La forme itérative utilise une pile explicite et devient nécessaire sur les graphes assez profonds pour saturer la pile d'appels, soit des chaînes de quelques dizaines de milliers de sommets.

Comment le DFS détecte-t-il un cycle?

Dans un graphe non orienté, une arête vers un sommet visité qui n'est pas le parent ferme un cycle. Dans un graphe orienté, il faut suivre les sommets présents dans la pile de récursion courante, car seule une arête revenant dans la pile est une vraie arête arrière. Une arête vers un sommet terminé est transverse ou avant et ne prouve rien.

Pourquoi le DFS consomme-t-il moins de mémoire que le BFS?

DFS ne conserve que le chemin courant de la racine au sommet, sa mémoire est donc proportionnelle à la profondeur. BFS conserve une frontière entière, qui sur un graphe large peut représenter une grande part de tous les sommets. Sur un graphe profond et étroit, la comparaison s'inverse et BFS devient le choix le plus léger.