Time and Space Complexity
Leçon 7 sur 9 du cours Parcours en profondeur - Algorithmes de graphes de Coddy.
Complexité temporelle :
- O(V + E)
- La construction de la liste d'adjacence parcourt chaque arête une fois, et le parcours visite chaque sommet et examine chaque arête un nombre constant de fois.
Complexité spatiale :
- O(V + E)
- La liste d'adjacence stocke chaque arête, et le tableau des sommets visités ainsi que la pile contiennent chacun jusqu'à V sommets.
Résumé :
- Le DFS explore d'abord en profondeur, en revenant sur ses pas lorsqu'il n'y a plus de voisins non visités.
- Il s'exécute en temps linéaire et constitue la base de nombreux algorithmes de graphes.
Essayez vous-même
Cette leçon ne comprend pas de défi de code.
Testez-vousCette leçon comprend un petit quiz. Commencez la leçon pour y répondre et suivre votre progression.
Toutes les leçons de Parcours en profondeur - Algorithmes de graphes
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity