Временная сложность
O(V + E)
DFS — это алгоритм обхода графа, который исследует каждую ветвь максимально глубоко, прежде чем вернуться назад (выполнить возврат). Для работы он использует стек или рекурсию.
Как это работает:
1. Начать с исходной вершины и отметить её как посещённую
2. Рекурсивно посетить каждого ещё не посещённого соседа
3. Вернуться назад, если непосещённых соседей больше нет
4. Продолжать, пока все достижимые вершины не будут посещены
Временная сложность: O(V + E)
V = количество вершин, E = количество рёбер
Пространственная сложность: O(V) — для стека рекурсии и множества посещённых вершин
Применение:
- Обнаружение циклов в графах
- Топологическая сортировка
- Поиск компонент связности
- Решение лабиринтов и головоломок
- Поиск путей
DFS сначала исследует наиболее глубокие пути. Это делает его полезным для топологической сортировки и обнаружения циклов, однако он не гарантирует нахождение кратчайшего пути.
Похожие алгоритмы
Частые вопросы
- Что такое Поиск в глубину (Depth-First Search, DFS)?
- DFS — это алгоритм обхода графа, который исследует каждую ветвь максимально глубоко, прежде чем вернуться назад (выполнить возврат). Для работы он использует стек или рекурсию.
- Какова сложность Поиск в глубину (Depth-First Search, DFS)?
- Время (среднее): O(V + E) · Память: O(V)
- Для кого предназначена визуализация Поиск в глубину (Depth-First Search, DFS)?
- Визуализация Поиск в глубину (Depth-First Search, DFS) рассчитана на средний уровень в категории «Графы». Полезна для студентов, подготовки к собеседованиям и практического изучения.
- Какие алгоритмы связаны с Поиск в глубину (Depth-First Search, DFS)?
- В той же категории (Графы) вы можете изучить: Breadth-First Search, Dijkstra's Algorithm, Prim's Algorithm. Каждый из них имеет интерактивную визуализацию.