- Actuel
- Dans la pile
- Terminé
- Chemin
Parcours en profondeur (DFS)
Le parcours en profondeur explore un graphe comme quelqu'un qui traverse un labyrinthe une main sur le mur : il suit un chemin aussi loin que possible et ne revient en arrière que lorsqu'il n'y a plus rien de nouveau. Pour cela, il utilise une pile. Cliquez sur un nœud pour partir de lui, choisissez une cible si vous voulez, et avancez pas à pas pour voir la pile grandir et rétrécir, chaque nœud recevoir son numéro de visite, et les arêtes qui ferment un cycle. Appuyez sur Lecture pour suivre le parcours, ou sur Étape et Retour pour avancer pas à pas. Faites glisser le curseur d'étapes pour aller n'importe où. Cliquez sur un nœud pour en faire le départ ; basculez le clic sur Cible et cliquez sur un autre nœud pour chercher un chemin jusqu'à lui. Le nombre sur chaque nœud est son rang dans l'ordre de visite, et la ligne sous le graphe est la pile, du départ jusqu'au nœud au sommet. Nouveau graphe crée un autre graphe ; choisissez son nombre de nœuds et d'arêtes. Quand le plateau est sélectionné, les flèches avancent ou reculent d'une étape, la barre d'espace lance et met en pause, et Origine et Fin vont au début et à la fin.
Comment ça marche
- Cliquez sur un nœud pour en faire le départ. Pour chercher un chemin, basculez le clic sur Cible et cliquez sur un autre nœud.
- Appuyez sur Lecture, ou utilisez Étape et Retour pour avancer pas à pas. Faites glisser le curseur d'étapes pour aller n'importe où dans le parcours.
- Observez la pile sous le graphe et le numéro de visite sur chaque nœud. Nouveau graphe crée un autre graphe à essayer.
Comment fonctionne le parcours en profondeur
Placez le nœud de départ dans la pile. Puis répétez : regardez le voisin suivant du nœud au sommet de la pile. Un voisin pas encore vu reçoit le numéro de visite suivant, retient le nœud depuis lequel il a été atteint, et passe au sommet de la pile, si bien que le parcours repart de là. Quand le nœud au sommet n'a plus de voisins à examiner, il est terminé et sort de la pile, et le parcours revient au nœud en dessous. Quand la pile est vide, chaque nœud accessible a été visité.
Ce que dit la pile
Comme le parcours repart toujours du nœud le plus récent, la pile est toujours un chemin du départ jusqu'au nœud examiné. Quand la cible est atteinte, la pile est un chemin jusqu'à elle, mais en général pas le plus court : c'est le parcours en largeur qui le trouve. Dans un graphe non orienté, une arête vers un nœud encore dans la pile, autre que celui d'où l'on vient, ferme un cycle. Les nœuds retenus forment un arbre, l'arbre du parcours en profondeur, et l'ordre dans lequel les nœuds sont terminés est la clé du tri topologique.
Questions fréquemment posées
Qu'est-ce que le parcours en profondeur ?
Une façon d'explorer un graphe depuis un nœud de départ en suivant un chemin aussi loin que possible, et en ne revenant en arrière pour essayer une autre branche que lorsqu'il n'y a plus rien de nouveau. Il utilise une pile, ou la récursivité, pour retenir le chemin du retour.
Le parcours en profondeur trouve-t-il le plus court chemin ?
Non. Il trouve un chemin jusqu'à la cible s'il en existe un, mais ce chemin peut être bien plus long que nécessaire, car le DFS s'engage dans la première branche qu'il essaie. Utilisez le parcours en largeur pour avoir le moins d'arêtes, ou l'algorithme de Dijkstra quand les arêtes ont des longueurs.
Quelle est la différence entre DFS et BFS ?
Le parcours en profondeur utilise une pile et va loin le long d'un chemin avant de revenir en arrière. Le parcours en largeur utilise une file et s'étend régulièrement, anneau par anneau. Tous deux visitent chaque nœud accessible en un temps qui croît avec le nombre de nœuds plus le nombre d'arêtes ; le BFS trouve les plus courts chemins, tandis que le DFS est le choix naturel pour les cycles, les labyrinthes et le tri topologique.
Comment le DFS trouve-t-il un cycle ?
Dans un graphe non orienté, si le parcours rencontre une arête vers un nœud encore dans la pile, et que ce nœud n'est pas celui d'où il vient, l'arête ferme une boucle. Dans l'application, la ligne d'état le signale quand cela arrive.
Mon graphe est-il envoyé quelque part ?
Non. Le graphe est créé et parcouru dans votre navigateur, et vos derniers réglages restent dans le stockage local de ce navigateur.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Aller à l'éditeur