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.
- O(V + E)
- espace O(V)
- pile
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.
Pile : dernier entré, premier sorti. DFS repart toujours du dernier sommet atteint.
Autres termes de cette page
- 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.
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.