DFS, рекурсия и итеративные стеки
Исследуйте граф в глубину и избегайте лимитов рекурсии
«DFS, рекурсия и итеративные стеки» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Что делает DFS
DFS углубляется настолько далеко, насколько может, по одному пути, затем возвращается назад и пробует следующий. Представьте исследование лабиринта, коридор за коридором. 🧭
DFS и BFS
BFS распространяется слоями, а DFS сначала углубляется. Оба обходят все достижимые вершины, но в совершенно разном порядке.
Рекурсивная структура
Рекурсивный DFS отмечает вершину как посещённую, а затем вызывает себя для каждого непосещённого соседа. Стек вызовов запоминает, куда нужно вернуться.
def dfs(u):
visited[u] = True
for v in adj[u]:
if not visited[v]:
dfs(v)Отмечайте до рекурсивного вызова
Устанавливайте отметку посещённости при входе в вершину, до исследования соседей. Иначе циклы отправят DFS в бесконечную рекурсию.
Ловушка ограничения рекурсии
Python ограничивает глубину рекурсии примерно 1000 вызовами. Глубокий граф вызывает RecursionError, который отображается как ошибка времени выполнения.
Увеличение ограничения
Быстрое решение — увеличить ограничение с помощью setrecursionlimit. Перед запуском DFS задайте значение больше глубины в худшем случае.
import sys
sys.setrecursionlimit(300000)Вместо этого используйте итеративный обход
Самое надёжное решение — итеративный DFS с собственным стеком. При отсутствии глубины вызовов сбой из-за рекурсии невозможен.
stack = [start]Извлечение из стека
На каждом шаге извлекайте верхний элемент стека. Принцип «последним вошёл — первым вышел» заставляет DFS сначала углубляться по самому недавно выбранному пути.
u = stack.pop()Добавление соседей в стек
После извлечения u добавьте каждого непосещённого соседа в стек. Отметьте их, чтобы не добавлять повторно.
for v in adj[u]:
if not visited[v]:
visited[v] = True
stack.append(v)Полный итеративный цикл
Повторяйте извлечение и добавление, пока в стеке есть вершины. Когда стек опустеет, все достижимые вершины будут посещены.
while stack:
u = stack.pop()
for v in adj[u]:
if not visited[v]:
visited[v] = True
stack.append(v)Та же сложность, что и у BFS
Как и BFS, DFS посещает каждую вершину и каждое ребро один раз, поэтому работает за O(n + m). Выбирайте алгоритм в зависимости от подходящего для задачи порядка обхода.
Быстрая проверка
Рекурсивный DFS завершается с ошибкой на глубоком графе. Почему?
Повторение
Вы запускаете DFS рекурсивно или с собственным стеком, отмечаете вершину при входе и переходите к итеративному варианту, когда граф становится глубоким. 🎉
Часто задаваемые вопросы
Урок «DFS, рекурсия и итеративные стеки» бесплатный?
Да — полный текст урока «DFS, рекурсия и итеративные стеки» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «DFS, рекурсия и итеративные стеки»?
Исследуйте граф в глубину и избегайте лимитов рекурсии Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.
Сколько времени занимает урок «DFS, рекурсия и итеративные стеки»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Списки смежности из входных данных
- BFS для кратчайших невзвешенных путей
- DFS, рекурсия и итеративные стеки
- Связные компоненты и заливка