Обход графа в Python: как реализовать BFS и DFS на списках смежности

Обход графа отвечает на простой вопрос: какие вершины достижимы из выбранной точки и в каком порядке их рассматривать? Два основных подхода — поиск в ширину, BFS, и поиск в глубину, DFS. Их удобнее понимать на одном небольшом графе, прослеживая очередь, стек и отметки посещения.

Ниже — авторские учебные реализации на Python 3 без сторонних библиотек. Вершины обозначены строками, граф конечный, невзвешенный и записан списками смежности. Каждая вершина, включая изолированную, присутствует ключом словаря. Эти условия позволяют сосредоточиться на алгоритме, а не на проверке произвольного входного формата.

Как читать список смежности

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C'],
    'X': []
}

Из A можно перейти в B и C, из B — в A и D. В примере рёбра неориентированные, поэтому каждое направление записано у обоих концов. X существует отдельно и ни с кем не соединена. Если вы описываете ориентированный граф, обратное ребро автоматически не возникает: в список нужно включать только разрешённые переходы.

Здесь есть цикл A → B → D → C → A. Поэтому обычная рекурсивная прогулка «идти ко всем соседям» без отметок будет снова возвращаться в уже пройденные места. Дерево — частный вид структуры, а произвольный граф требует учитывать повторные связи.

BFS: очередь хранит следующий слой

Для очереди используем collections.deque: добавляем справа через append(), извлекаем слева через popleft(). Документация Python специально рекомендует deque для таких операций очереди. Список с удалением первого элемента заставляет сдвигать остальные элементы, поэтому для этой роли он менее подходящая базовая конструкция.

from collections import deque

def bfs(graph, start):
    if start not in graph:
        raise ValueError('Неизвестная начальная вершина')
    queue = deque([start])
    visited = {start}
    parent = {start: None}
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                parent[neighbor] = node
                queue.append(neighbor)
    return order, parent

order, parent = bfs(graph, 'A')
print(order)  # ['A', 'B', 'C', 'D']

Сначала извлекается A, после неё очередь содержит B и C. При обработке B обнаруживается D и добавляется после C. Когда дойдём до C, D уже отмечена, поэтому второй раз в очередь не попадёт. Обратите внимание: отметка ставится при добавлении в очередь, а не после извлечения. Это исключает дублирующее ожидание одной вершины через разных родителей.

Порядок соседей влияет на конкретный порядок обхода. Если записать C перед B, некоторые результаты будут другими. Это не ошибка, если соблюдается смысл обхода. Для воспроизводимого примера здесь используются упорядоченные списки, а не наборы соседей без заданной последовательности.

Восстановление пути по родителям

Словарь parent хранит, откуда вершина впервые обнаружена. Для невзвешенного графа BFS подходит для поиска пути с минимальным числом рёбер. Это не то же самое, что минимальная стоимость: если переходы имеют разные веса, нужен подходящий алгоритм для взвешенной задачи.

def restore_path(parent, target):
    if target not in parent:
        return None
    path = []
    node = target
    while node is not None:
        path.append(node)
        node = parent[node]
    return path[::-1]

print(restore_path(parent, 'D'))  # ['A', 'B', 'D']
print(restore_path(parent, 'A'))  # ['A']
print(restore_path(parent, 'X'))  # None

У D родитель B, у B — A, у A стоит маркер None. Собранный обратный путь разворачиваем. Результат None означает, что в полученном дереве обхода нет цели: например, X недостижима из A. Это отличается от пути из A в саму A, который содержит одну вершину и ноль рёбер.

В этой реализации None зарезервирован как признак отсутствия родителя, а вершины — строки. Если в вашей модели None может быть настоящей вершиной, выберите отдельный маркер или другую схему завершения восстановления. Условие входного формата здесь является частью алгоритма.

DFS с явным стеком

Стек работает по принципу «последним добавлен — первым извлечён». Для него подходит обычный список с append() и pop() на конце. Следующий учебный вариант помещает соседей в обратном порядке, чтобы первым рассматривать левого соседа из исходного списка:

def dfs_stack(graph, start):
    if start not in graph:
        raise ValueError('Неизвестная начальная вершина')
    stack = [start]
    visited = set()
    order = []
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        stack.extend(reversed(graph[node]))
    return order

print(dfs_stack(graph, 'A'))  # ['A', 'B', 'D', 'C']

Здесь одна вершина может оказаться в стеке несколько раз, но проверка перед обработкой пропускает повтор. Это свойство именно показанного простого варианта; не переносите автоматически на него утверждение «в стеке всегда каждая вершина ровно один раз». Если важна память на большом графе, анализируйте представление состояния и количество отложенных элементов.

DFS через рекурсию

Рекурсивная запись делает переход к соседу непосредственным вызовом функции. Отмечаем вершину до спуска, чтобы цикл не возвращал нас к незавершённой работе:

def dfs_recursive(graph, start, visited=None):
    if start not in graph:
        raise ValueError('Неизвестная начальная вершина')
    if visited is None:
        visited = set()
    order = []

    def visit(node):
        if node in visited:
            return
        visited.add(node)
        order.append(node)
        for neighbor in graph[node]:
            visit(neighbor)

    visit(start)
    return order

print(dfs_recursive(graph, 'A'))  # ['A', 'B', 'D', 'C']

Обратите внимание на visited=None в параметрах. Новое множество создаётся при обычном отдельном вызове; при необходимости можно явно передать общее состояние. Это позволяет не смешивать независимые обходы и в то же время повторно использовать функцию для всего несвязного графа.

В Python глубина рекурсии ограничена. Длинная цепочка вершин может привести к RecursionError, даже если циклы обработаны правильно. Повышение лимита не является универсальным исправлением. Для глубокой структуры рассмотрите явный стек: он убирает зависимость обхода от глубины вложенных вызовов Python, хотя память для состояния всё равно нужна.

Как пройти несвязный граф целиком

Один запуск из A не посещает X. Для нашего неориентированного примера переберём все вершины и начнём новый DFS там, где общей отметки ещё нет:

seen = set()
components = []
for node in graph:
    if node not in seen:
        components.append(dfs_recursive(graph, node, seen))
print(components)  # [['A', 'B', 'D', 'C'], ['X']]

Получились две компоненты связности. Общее множество seen не даёт заново обходить уже найденную компоненту. Для ориентированного графа понятия сильной и слабой связности требуют отдельного определения и алгоритма; такой простой разбор достижимости нельзя без оговорки назвать поиском всех сильно связных компонент.

Что выбрать для задачи

Задача	Начальный выбор	Что проверить
Минимум переходов в невзвешенной сети	BFS с родителями	Все рёбра считаются одинаковыми по стоимости
Обойти достижимую область с углублением	DFS	Отметки посещения и порядок соседей
Очень глубокая структура	DFS с явным стеком	Память стека и повторы отложенных вершин
Полный обход несвязной сети	Внешний цикл с общими отметками	Ориентированность и нужное понятие связности

У BFS очередь может стать широкой, если на очередном уровне много вершин. Рекурсивный DFS хранит цепочку вызовов, а приведённый итеративный вариант — отложенных соседей. Поэтому нельзя обещать, что один обход всегда потребляет меньше памяти другого: это зависит от графа и конкретной реализации.

Проверьте функции на цикле, изолированной вершине, пути в начальную вершину и недостижимой цели. Затем поменяйте порядок соседей и сравните результаты. Так становится видно, что является обязательным свойством алгоритма, а что — особенностью выбранного порядка и учебной записи графа.