Поиск в глубину (DFS) в Python
В этом уроке вы обойдёте граф с помощью поиска в глубину, реализованного рекурсивной функцией.
Введение
Какую задачу это решает
Поиск выхода из лабиринта, проверка графа на циклы или упорядочивание задач, зависящих друг от друга, - всё это требует пройти по одному пути до конца, прежде чем пробовать другой. Это и есть поиск в глубину.
Пример из жизни
Поиск в глубину - это то, как исследуют пещеру с клубком нити. Вы идёте по одному туннелю так глубоко, как он ведёт. В тупике вы возвращаетесь по нити к последней развилке и пробуете следующий туннель. Исследованные туннели вы помечаете, чтобы не проходить их дважды.
visited.add(node)🧵 Пометить туннель как исследованныйfor neighbor in graph[node]:🔀 Посмотреть на каждый туннель отсюдаdepth_first(neighbor, visited)⬇️ Пойти глубже в первый неисследованныйreturn order↩️ Тупик: вернуться по нитиПоиск в глубину (DFS) исследует граф, проходя по одной ветке как можно глубже, прежде чем вернуться, обычно с помощью рекурсии или стека.
Главное
visited.add(node)помечает узел, поэтому циклы не вызывают бесконечную рекурсию.for neighbor in graph[node]:по очереди смотрит на каждого соседа.order.extend(depth_first(neighbor, visited))исследует всю ветку под соседом до перехода к следующему.- Результат посещает D раньше C, потому что ветка B заканчивается первой.
Когда это нужно?
- Поиск любого пути, решение лабиринтов и головоломок перебором с возвратом.
- Поиск циклов и упорядочивание задач с зависимостями (топологическая сортировка).
- Исследование всех связных частей графа.
Когда это не нужно
- Нужен кратчайший путь: поиск в глубину может сначала найти длинный путь; используйте поиск в ширину.
- Очень глубокие графы: рекурсия может упереться в предел Python; используйте явный стек.
Визуализация: Поиск в глубину (DFS) в Python
O(V + E)Нажимайте Запуск или Шаг, чтобы следить за сравнениями и перемещением данных.
Пример кода
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.
Упражнения для практики
Попробуйте изменить код по подсказкам ниже. Если менять код и смотреть на результат, урок запомнится гораздо лучше, чем при простом чтении.
- Проверьте работу на пустом списке, списке из одного элемента и списке с повторами.
- Выводите состояние после каждого шага, чтобы увидеть алгоритм в действии.
- Измерьте время работы на 100, 1 000 и 10 000 элементах и сравните с другим решением.
Частые ошибки
Изменяемый аргумент по умолчанию
visited=set() был бы общим для отдельных вызовов.
def depth_first(node, visited=set()):
def depth_first(node, visited=None):
visited = visited or set()
Закончили этот урок?
Отметьте его как изученный, чтобы следить за прогрессом.
Попрактикуйтесь на задаче
Примените материал этого урока к реальной задаче. Каждая задача запускается в браузере, с мгновенными тестами и разбором от ИИ.
- Count Islands Count groups of connected land cells in a grid. Средне
- Strongly Connected Components Count groups of nodes that can all reach each other. Сложно
- Longest Path in a DAG Find the heaviest path in a task dependency graph. Сложно