Time and Space Complexity
Урок 7 из 9 курса Поиск в ширину — Алгоритмы на графах на Coddy.
Временная сложность:
- O(V + E)
- Каждая вершина помещается в очередь и извлекается из нее один раз, а каждое ребро проверяется константное количество раз.
Пространственная сложность:
- O(V + E)
- Список смежности хранит каждое ребро, а очередь и массив посещенных вершин содержат до V вершин.
Итог:
- BFS исследует граф по слоям, используя очередь, посещая ближайшие вершины перед более удаленными.
- Такой послойный порядок делает его основным алгоритмом для поиска кратчайших путей в невзвешенных графах.
Попробуйте сами
В этом уроке нет задания по программированию.
Проверьте себяВ этом уроке есть небольшой тест. Начните урок, чтобы ответить на вопросы и сохранить прогресс.
Все уроки раздела Поиск в ширину — Алгоритмы на графах
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity