Parcours en profondeur (DFS)
Explore un graphe en suivant un chemin aussi loin que possible, puis revient au dernier embranchement. La pile à l'écran, c'est ce chemin.
- temps O(V + E)
- espace O(V)
- utilise une pile
Que veulent dire ces termes ?
- Sommet : un point du graphe, dessiné ici comme un cercle avec une lettre.
- Arête : une ligne qui relie deux sommets. Ici, on peut la parcourir dans les deux sens.
- Voisins : les sommets reliés à un sommet par une arête. On les examine dans l'ordre alphabétique.
- File : premier entré, premier sorti. BFS prend toujours le sommet qui attend depuis le plus longtemps.
- Pile : dernier entré, premier sorti. DFS repart toujours du dernier sommet atteint.
- V et E : le nombre de sommets et d'arêtes. O(V + E) veut dire que chaque sommet et chaque arête sont traités un nombre fixe de fois.
- sur la pile
- en cours
- traité
- arête de l'arbre de parcours
- arête ignorée
Départ de A. Appuyez sur Lire ou avancez pas à pas.
Espace : lecture ou pause. Flèches gauche et droite : pas à pas. Origine et Fin : sauter.
Essayez : Choisissez le graphe avec cycles. Chaque arête en pointillés ramène à un sommet déjà sur la pile ou déjà traité : cette arête ferme un cycle.
Comment ça marche
DFS s'appelle lui-même sur le premier voisin pas encore vu, puis sur le premier nouveau voisin de ce sommet, et ainsi de suite. Quand un sommet n'a plus de nouveaux voisins, son appel se termine et DFS recule d'un pas pour essayer le voisin suivant. Les appels ouverts forment une pile, qui est toujours le chemin du départ jusqu'au sommet actuel. Le nombre à côté d'un sommet indique dans quel ordre il a été visité.
Quand le choisir
Utilisez DFS pour savoir ce qui est atteignable, pour trouver des cycles, pour parcourir un labyrinthe ou pour mettre dans l'ordre des tâches qui dépendent les unes des autres. Il ne trouve pas le chemin le plus court.