Алгоритмы на Python

Поиск в глубину (DFS) в Python

В этом уроке вы обойдёте граф с помощью поиска в глубину, реализованного рекурсивной функцией.

  • Средний
  • Чтение: 2 мин
  • Примеров для запуска: 1

Введение

Какую задачу это решает

Поиск выхода из лабиринта, проверка графа на циклы или упорядочивание задач, зависящих друг от друга, - всё это требует пройти по одному пути до конца, прежде чем пробовать другой. Это и есть поиск в глубину.

Пример из жизни

Поиск в глубину - это то, как исследуют пещеру с клубком нити. Вы идёте по одному туннелю так глубоко, как он ведёт. В тупике вы возвращаетесь по нити к последней развилке и пробуете следующий туннель. Исследованные туннели вы помечаете, чтобы не проходить их дважды.

От исследования пещеры к коду
visited.add(node)🧵 Пометить туннель как исследованный
for neighbor in graph[node]:🔀 Посмотреть на каждый туннель отсюда
depth_first(neighbor, visited)⬇️ Пойти глубже в первый неисследованный
return order↩️ Тупик: вернуться по нити
Сначала вглубь, потом назад и следующая ветка.
Одним предложением

Поиск в глубину (DFS) исследует граф, проходя по одной ветке как можно глубже, прежде чем вернуться, обычно с помощью рекурсии или стека.

Главное

  1. visited.add(node) помечает узел, поэтому циклы не вызывают бесконечную рекурсию.
  2. for neighbor in graph[node]: по очереди смотрит на каждого соседа.
  3. order.extend(depth_first(neighbor, visited)) исследует всю ветку под соседом до перехода к следующему.
  4. Результат посещает D раньше C, потому что ветка B заканчивается первой.

Когда это нужно?

  • Поиск любого пути, решение лабиринтов и головоломок перебором с возвратом.
  • Поиск циклов и упорядочивание задач с зависимостями (топологическая сортировка).
  • Исследование всех связных частей графа.

Когда это не нужно

  • Нужен кратчайший путь: поиск в глубину может сначала найти длинный путь; используйте поиск в ширину.
  • Очень глубокие графы: рекурсия может упереться в предел Python; используйте явный стек.

Визуализация: Поиск в глубину (DFS) в Python

O(V + E)

Нажимайте Запуск или Шаг, чтобы следить за сравнениями и перемещением данных.

Пример кода

Запустить код →
main.py
graph = {"A": ["B", "C"], "B": ["D"], "C": ["E"], "D": [], "E": []}

def depth_first(node, visited=None):
    visited = visited or set()
    visited.add(node)
    order = [node]
    for neighbor in graph[node]:
        if neighbor not in visited:
            order.extend(depth_first(neighbor, visited))
    return order

print(depth_first("A"))
Получить кнопку запуска для этого примера

Результат выполнения

['A', 'B', 'D', 'C', 'E']

Разбор кода

Множество visited запоминает посещённые вершины, чтобы избежать повторов и бесконечных циклов, когда в графе есть циклы. Каждый рекурсивный вызов спускается в ещё не посещённого соседа, поэтому программа посещает A, B, D, а потом возвращается и посещает C и E. Роль стека алгоритма играет стек вызовов, а сложность O(V + E).

Измените значения и запустите программу в онлайн-компиляторе Python CodeUtility без локальной установки Python.

Упражнения для практики

Попробуйте изменить код по подсказкам ниже. Если менять код и смотреть на результат, урок запомнится гораздо лучше, чем при простом чтении.

  1. Проверьте работу на пустом списке, списке из одного элемента и списке с повторами.
  2. Выводите состояние после каждого шага, чтобы увидеть алгоритм в действии.
  3. Измерьте время работы на 100, 1 000 и 10 000 элементах и сравните с другим решением.
Запустить в компиляторе Python →

Частые ошибки

Изменяемый аргумент по умолчанию

visited=set() был бы общим для отдельных вызовов.

Ошибка
def depth_first(node, visited=set()):
Исправление
def depth_first(node, visited=None):
    visited = visited or set()

Закончили этот урок?

Отметьте его как изученный, чтобы следить за прогрессом.

Попрактикуйтесь на задаче

Примените материал этого урока к реальной задаче. Каждая задача запускается в браузере, с мгновенными тестами и разбором от ИИ.

Все задачи