Time and Space Complexity
Leçon 7 sur 9 du cours Parcours en largeur - Algorithmes de graphes de Coddy.
Complexité temporelle :
- O(V + E)
- Chaque sommet est mis en file d'attente et retiré de la file une seule fois, et chaque arête est examinée un nombre constant de fois.
Complexité spatiale :
- O(V + E)
- La liste d'adjacence stocke chaque arête, et la file d'attente ainsi que le tableau des sommets visités contiennent jusqu'à V sommets.
Résumé :
- Le BFS explore par couches en utilisant une file d'attente, visitant les sommets les plus proches avant les plus éloignés.
- Cet ordre par couches en fait l'algorithme de référence pour les plus courts chemins dans les graphes non pondérés.
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 largeur - Algorithmes de graphes
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity