Aller au contenu

TNSI : Parcours en Profondeur
ou DFS - Depth First Search 🇬🇧⚓︎

Introduction⚓︎

Introduction (15 min 22)


Implémentation Itérative avec une Pile⚓︎

Implémentation Itérative avec une Pile (4 min 54)


Implémentation Récursive du Parcours en Profondeur⚓︎

Implémentation Récursive du Parcours en Profondeur (35 min 16)

Résumé⚓︎

1⃣ Un Parcours en Profondeur 🇫🇷 ou DFS - Depth First Search 🇬🇧 peut être implémenté par un Algorithme :

  • Itératif, avec une Pile
  • Récursif, avec une Pile d'appels récursifs

2⃣ Un Parcours en Profondeur (DFS) permet de:

  • Construire un Arbre Couvrant (en général non minimal)
  • Construire un chemin entre un sommet de départ (racine) et tous les autres sommets (atteignables)
  • Déterminer si le graphe est Connexe, ou pas
  • Déterminer si le graphe admet un Cycle, ou pas

3⃣ un Parcours en Profondeur fonctionne aussi bien pour des Graphes Orientés, que Non Orientés