Français
Menu

Qu'est-ce que Parcours en profondeur (depth-first search) ?

Méthode d'exploration d'un graphe ou d'un arbre qui avance le plus loin possible le long d'un chemin et revient en arrière pour essayer un autre chemin quand elle atteint une impasse. Elle s'implémente par récursion ou avec une pile et sert à la résolution de labyrinthes, à la recherche de composantes connexes et de cycles, et au tri topologique. On l'abrège en DFS.

Nom japonais: 深さ優先探索

« Parcours en profondeur (depth-first search) » apparaît dans 3 questions d'entraînement réparties sur 1 thèmes, dont Structures de données et algorithmes.

Domaine: Structures de données et algorithmes

S'entraîner : questions sur Parcours en profondeur (depth-first search)

Dans un graphe non orienté, les voisins de chaque sommet sont A : B, C / B : A, D, E / C : A, F / D : B / E : B, F / F : C, E. Un parcours en profondeur par récursion part du sommet A. Les voisins sont examinés dans l'ordre indiqué, et dès qu'un sommet non visité est trouvé, le parcours s'y déplace. Dans quel ordre les sommets sont-ils visités ?

  1. AA, B, C, D, E, F
  2. BA, B, D, E, C, F
  3. CA, B, D, E, F, C
Afficher la réponse et l'explication

Réponse : C. A, B, D, E, F, C

Depuis A, le parcours passe à B, puis à D, le premier voisin non visité de B. Le seul voisin de D, B, est déjà visité : le parcours revient donc à B et passe à E, puis de E au sommet non visité F, et de F à son voisin C. L'ordre est donc A, B, D, E, F, C. A, B, C, D, E, F est l'ordre du parcours en largeur, qui visite d'abord les sommets les plus proches. A, B, D, E, C, F revient en arrière depuis E sans aller au sommet non visité F : ce n'est donc pas un ordre de parcours en profondeur.

« Parcours en profondeur (depth-first search) » dans les explications

Questions mentionnant « Parcours en profondeur (depth-first search) » (3)

  1. Dans un graphe non orienté, les voisins de chaque sommet sont A : B, C / B : A, D, E / C : A, F / D : B / E : B, F / F : C, E. Un parcours en profondeur par récursion part du sommet A. Les voisins sont examinés dans l'ordre indiqué, et dès qu'un sommet non visité est trouvé, le parcours s'y déplace. Dans quel ordre les sommets sont-ils visités ?
  2. Dans un graphe dont les arêtes n'ont pas de poids, on veut trouver le plus petit nombre d'arêtes entre un sommet de départ et chacun des autres sommets. Quelle association entre méthode de recherche et structure de données convient ?
  3. Les tâches A à E ont les contraintes d'ordre « A avant C », « B avant C », « C avant D », « B avant E » et « E avant D ». Quel ordre satisfait toutes les contraintes (résultat d'un tri topologique) ?

Termes associés

Récursion (récursivité) Parcours en largeur (breadth-first search) File d'attente Pile (stack) Algorithme de Dijkstra Algorithme glouton (greedy) Arbre binaire de recherche (binary search tree) Complexité temporelle (notation grand O) Liste chaînée (linked list) Programmation dynamique

Retour au glossaire