Обход графов: BFS и DFS с примерами кода

Коротко: в чём разница

BFS (обход в ширину) сначала посещает всех соседей стартовой вершины, потом соседей соседей и так далее. Он использует очередь и гарантирует, что в невзвешенном графе вершина будет найдена по кратчайшему пути.

DFS (обход в глубину) идёт по одной ветке до конца, затем откатывается назад. Он использует стек (явный или стек вызовов при рекурсии) и удобен там, где важна структура путей: циклы, компоненты связности, порядок зависимостей.

Оба алгоритма посещают каждую вершину и ребро один раз, их сложность — O(V + E), где V — число вершин, E — число рёбер.

Как хранить граф

В большинстве задач хватает словаря, где ключ — вершина, а значение — список соседей:

graph = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": ["D", "E"],
    "D": ["F"],
    "E": ["F"],
    "F": [],
}

BFS: кратчайший путь в невзвешенном графе

from collections import deque

def shortest_path(graph, start, goal):
    queue = deque([start])
    parent = {start: None}
    while queue:
        node = queue.popleft()
        if node == goal:
            path = []
            while node is not None:
                path.append(node)
                node = parent[node]
            return path[::-1]
        for nxt in graph[node]:
            if nxt not in parent:
                parent[nxt] = node
                queue.append(nxt)
    return None

Ключевые моменты:

• Вершина помечается посещённой в момент добавления в очередь, а не при извлечении — иначе она попадёт в очередь несколько раз.
• Словарь parent одновременно служит множеством посещённых и позволяет восстановить путь.
• Используйте deque: list.pop(0) в Python работает за линейное время.

Где применяется: маршрут с минимальным числом пересадок, «друзья друзей» в соцсети, обход сайта краулером по уровням вложенности, заливка области на сетке.

DFS: поиск цикла в ориентированном графе

Для ориентированного графа недостаточно знать «посещена ли вершина». Нужно три состояния: не посещена, в процессе (на текущем пути), завершена. Если мы встретили вершину «в процессе» — найден цикл.

def has_cycle(graph):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {v: WHITE for v in graph}

    def visit(v):
        color[v] = GRAY
        for nxt in graph[v]:
            if color[nxt] == GRAY:
                return True
            if color[nxt] == WHITE and visit(nxt):
                return True
        color[v] = BLACK
        return False

    return any(color[v] == WHITE and visit(v) for v in graph)

DFS: порядок зависимостей

Пакетные менеджеры, системы сборки и миграции БД решают одну задачу: выполнить шаги так, чтобы зависимость шла раньше зависимого. Это топологическая сортировка, и она строится на DFS: вершина добавляется в результат после того, как обработаны все её потомки, затем список разворачивается.

def topo_sort(graph):
    seen, order = set(), []
    def visit(v):
        seen.add(v)
        for nxt in graph[v]:
            if nxt not in seen:
                visit(nxt)
        order.append(v)
    for v in graph:
        if v not in seen:
            visit(v)
    return order[::-1]

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

Как выбрать

• Нужен кратчайший путь по числу шагов — BFS.
• Нужны циклы, компоненты, топологический порядок, перебор всех путей — DFS.
• У рёбер есть веса — ни один из них не подходит, нужен алгоритм Дейкстры или его аналоги.
• Граф очень глубокий — рекурсивный DFS может упереться в лимит стека, перепишите его на явный стек.

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

• Забыть про множество посещённых вершин — в графе с циклом обход станет бесконечным.
• Обойти только одну компоненту, когда граф несвязный. Запускайте обход от каждой непосещённой вершины.
• Использовать BFS для взвешенного графа и считать результат кратчайшим.
• Строить матрицу смежности для большого разреженного графа и тратить память впустую.