Обходы графа: BFS и DFS

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

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

Зачем это нужно

BFS и DFS — это «мотор» теории графов. На BFS строятся кратчайшие пути в невзвешенном графе, проверка двудольности, обход лабиринта. На DFS — поиск компонент связности, топологическая сортировка, поиск циклов, мостов и точек сочленения. Освоив эти два обхода, ты получаешь ключ к доброй половине графовых задач. Главное — понимать чем они отличаются и что гарантирует каждый.

BFS: обход в ширину

BFS использует очередь. Начинаем со старта, кладём его в очередь, затем многократно достаём вершину и добавляем всех её непосещённых соседей. Поскольку вершины обрабатываются в порядке добавления, граф «заливается волной»: сначала старт (расстояние 0), потом все его соседи (расстояние 1), потом их соседи (расстояние 2) и так далее. Это даёт ключевое свойство: BFS находит кратчайшие пути в невзвешенном графе.

from collections import deque

g = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2, 4], 4: [3]}

def bfs(start):
    dist = {start: 0}             # заодно служит множеством посещённых
    q = deque([start])
    order = []
    while q:
        u = q.popleft()           # берём из начала очереди (FIFO)
        order.append(u)
        for v in g[u]:
            if v not in dist:     # ещё не посещали
                dist[v] = dist[u] + 1
                q.append(v)
    return order, dist

order, dist = bfs(0)
print("BFS-порядок:", order)
print("Расстояния от 0:", dist)

Важная деталь: вершину помечаем посещённой в момент добавления в очередь (записывая dist), а не при извлечении — иначе одна вершина попадёт в очередь несколько раз. Каждая вершина и каждое ребро обрабатываются один раз: сложность O(n + m).

Вывод:

BFS-порядок: [0, 1, 2, 3, 4]
Расстояния от 0: {0: 0, 1: 1, 2: 1, 3: 2, 4: 3}

DFS: обход в глубину

DFS идёт «вглубь»: из вершины переходит к первому непосещённому соседу, оттуда — снова вглубь, и только упёршись, возвращается назад. Естественно пишется рекурсией, но на больших графах рекурсия упирается в лимит — поэтому полезно знать и итеративную версию на стеке.

import sys
sys.setrecursionlimit(1 << 20)     # на случай глубокой рекурсии

g = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2, 4], 4: [3]}

# Рекурсивный DFS
visited = set()
order = []
def dfs(u):
    visited.add(u)
    order.append(u)
    for v in g[u]:
        if v not in visited:
            dfs(v)
dfs(0)
print("DFS (рекурсия):", order)

# Итеративный DFS на стеке
def dfs_iter(start):
    seen = set([start])
    stack = [start]
    res = []
    while stack:
        u = stack.pop()           # берём с вершины стека (LIFO)
        res.append(u)
        for v in g[u]:
            if v not in seen:
                seen.add(v)
                stack.append(v)
    return res
print("DFS (стек):    ", dfs_iter(0))

Разница в одной структуре: BFS берёт из начала очереди (FIFO), DFS — с вершины стека (LIFO). Порядок итеративного DFS может отличаться от рекурсивного (соседи кладутся в стек в обратном порядке), но множество посещённых вершин одно и то же. Сложность тоже O(n + m).

Вывод:

DFS (рекурсия): [0, 1, 3, 2, 4]
DFS (стек):     [0, 2, 3, 4, 1]

BFS по лабиринту (сетке)

Очень частое применение BFS — кратчайший путь в лабиринте, где вершины — это клетки, а рёбра — переходы к соседним свободным клеткам. Найдём минимальное число шагов из угла в угол.

from collections import deque

grid = [
    "....",
    ".##.",
    ".#..",
    "...#",
]
R, C = len(grid), len(grid[0])
start, goal = (0, 0), (3, 2)
dist = [[-1] * C for _ in range(R)]
dist[start[0]][start[1]] = 0
q = deque([start])
while q:
    r, c = q.popleft()
    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nr, nc = r + dr, c + dc
        if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == "." and dist[nr][nc] == -1:
            dist[nr][nc] = dist[r][c] + 1
            q.append((nr, nc))
print("Кратчайший путь из угла:", dist[goal[0]][goal[1]])

Здесь четыре направления — это «рёбра» сетки; dist == -1 играет роль «не посещено». BFS гарантирует, что первое достижение клетки — кратчайшее.

Вывод:

Кратчайший путь из угла: 5

Применение BFS: проверка двудольности

Красивый пример силы обхода — проверка, можно ли раскрасить граф в два цвета так, чтобы соседи всегда были разного цвета (двудольный граф). Это задача о конфликтах: «можно ли разбить участников на две команды, чтобы никакие двое враждующих не попали в одну?». Идея: запускаем BFS, красим старт в цвет 0, всех его соседей — в цвет 1, их соседей — снова в 0, и так далее. Если встретили ребро между вершинами одного цвета — граф не двудольный.

from collections import deque

def is_bipartite(n, g):
    color = [-1] * n                   # -1 = ещё не покрашена
    for s in range(n):
        if color[s] != -1:
            continue
        color[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            for v in g[u]:
                if color[v] == -1:
                    color[v] = color[u] ^ 1   # противоположный цвет
                    q.append(v)
                elif color[v] == color[u]:
                    return False              # конфликт цветов
    return True

cycle4 = {0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2]}   # квадрат
triangle = {0: [1, 2], 1: [0, 2], 2: [0, 1]}            # треугольник
print("Цикл из 4 вершин двудольный?", is_bipartite(4, cycle4))
print("Треугольник двудольный?     ", is_bipartite(3, triangle))

Трюк color[u] ^ 1 переключает цвет между 0 и 1. Чётный цикл (квадрат) красится без конфликтов — он двудольный; нечётный (треугольник) — нет, потому что третья вершина обязательно столкнётся с уже покрашенным соседом своего цвета. Общий факт: граф двудолен тогда и только тогда, когда в нём нет циклов нечётной длины. Сложность — те же O(n + m), что у обычного обхода.

Вывод:

Цикл из 4 вершин двудольный? True
Треугольник двудольный?      False

BFS или DFS: что выбрать

Подводные камни

• BFS помечает при добавлении в очередь, не при извлечении — иначе вершины дублируются.
• Глубокая рекурсия DFS падает. Поднимай setrecursionlimit или используй итеративную версию на стеке.
• BFS даёт кратчайший путь только без весов (или при единичных весах). Для разных весов нужна Дейкстра — следующая тема.

Итог

• BFS (очередь) обходит граф слоями и находит кратчайшие пути в невзвешенном графе за O(n+m).
• DFS (рекурсия или стек) уходит вглубь; основа топосортировки, поиска циклов, компонент.
• Помечай вершину посещённой вовремя; для больших графов избегай переполнения стека рекурсии.
• Для взвешенных графов BFS не годится — нужна Дейкстра.