Motivation
Урок 2 из 9 курса Поиск в глубину — алгоритмы на графах на Coddy.
DFS исследует граф, выбирая путь и следуя по нему до упора, а затем возвращается к последней вершине с неисследованным соседом.
Зачем изучать DFS?
- Фундаментальность: он лежит в основе обнаружения циклов, топологической сортировки, поиска компонентов связности и многих других алгоритмов.
- Простота и эффективность: он работает за время O(V + E), используя стек (или рекурсию) и метку посещения.
- Универсальность: один и тот же обход отвечает на такие вопросы, как «связаны ли эти две вершины?» и «из скольких отдельных частей состоит граф?»
Чтобы результаты были предсказуемыми, мы всегда посещаем соседей вершины в порядке возрастания.
Попробуйте сами
В этом уроке нет задания по программированию.
Проверьте себяВ этом уроке есть небольшой тест. Начните урок, чтобы ответить на вопросы и сохранить прогресс.
