Время одинаковое, память — разная

BFS и DFS по времени одинаковы: O(V + E). По памяти — разные, и характер этой разницы зависит от формы графа. Этот урок — про то, как форма графа влияет на потребление RAM при обходе и как выбирать алгоритм осознанно.

Что хранит каждый

Структуры, которые «потребляют» память:

• visited — оба алгоритма. O(V) в обоих случаях.
• queue (BFS) — содержит вершины «фронта»: те, которые открыли, но ещё не извлекли.
• stack (DFS) — содержит вершины «текущего пути»: те, по которым мы сейчас спускаемся.

Visited — одинаков. Разница в queue vs stack.

BFS: память на фронте

В BFS в queue одновременно лежит весь текущий уровень, плюс часть следующего. Сколько это?

Возьмём «звезду» (Star graph): одна центральная вершина и V-1 листьев вокруг.

• BFS из центра: после извлечения центра в queue окажутся все V-1 листьев одновременно.
• Память queue = O(V).

Возьмём «верёвку» (Path graph): 1 -> 2 -> 3 -> … -> V.

• BFS: на каждом шаге в queue 1-2 вершины.
• Память queue = O(1).

Возьмём сбалансированное бинарное дерево из N вершин:

• BFS: на самом широком уровне (~N/2 листьев) очередь содержит ~N/2 вершин.
• Память queue = O(N).

Возьмём «куст»: вершина имеет 100 детей, каждый из них — ещё 100 детей. На 3 уровнях — 1 + 100 + 10000 + 1 000 000 вершин.

• BFS: после уровня 3 в queue окажется ~1 миллион вершин одновременно.
• Память queue = O(огромная).

Правило: память BFS = ширина самого широкого уровня. Это может быть как O(1), так и O(V) — зависит от формы.

DFS: память на глубине

В DFS в stack лежит путь от старта до текущей вершины. Глубина рекурсии или явного stack.

«Звезда»:

• DFS: спустились в один лист, вернулись. Глубина стека = 2.
• Память stack = O(1).

«Верёвка»:

• DFS: спускаемся до конца. Глубина = V.
• Память stack = O(V) — рискованно для длинных верёвок.

Сбалансированное бинарное дерево из N вершин:

• DFS: глубина = log N.
• Память stack = O(log N).

«Куст» (100 детей у каждой вершины, глубина 3):

• DFS: глубина = 3.
• Память stack = O(1).

Правило: память DFS = высота дерева DFS, то есть длина самого длинного пути от старта до листа.

Реальные числа на 100k вершин

Cделаем бенчмарк на разных формах графа:

from collections import defaultdict, deque
import sys

def bfs(adj, start):
    visited = {start}
    q = deque([start])
    max_q = 1
    while q:
        max_q = max(max_q, len(q))
        u = q.popleft()
        for v in adj.get(u, []):
            if v not in visited:
                visited.add(v)
                q.append(v)
    return max_q

def dfs(adj, start):
    visited = set()
    stack = [start]
    max_s = 1
    while stack:
        max_s = max(max_s, len(stack))
        u = stack.pop()
        if u in visited:
            continue
        visited.add(u)
        for v in adj.get(u, []):
            if v not in visited:
                stack.append(v)
    return max_s

# Граф 1: звезда
adj_star = defaultdict(list)
N = 100_000
for i in range(1, N):
    adj_star[0].append(i)

print("star BFS max queue:", bfs(adj_star, 0))   # ~99999
print("star DFS max stack:", dfs(adj_star, 0))   # ~99999

# Граф 2: верёвка
adj_path = defaultdict(list)
for i in range(N - 1):
    adj_path[i].append(i + 1)

print("path BFS max queue:", bfs(adj_path, 0))   # 1
print("path DFS max stack:", dfs(adj_path, 0))   # 99999

# Граф 3: бинарное дерево
adj_tree = defaultdict(list)
for i in range(N):
    if 2*i + 1 < N: adj_tree[i].append(2*i + 1)
    if 2*i + 2 < N: adj_tree[i].append(2*i + 2)

print("tree BFS max queue:", bfs(adj_tree, 0))   # ~25000
print("tree DFS max stack:", dfs(adj_tree, 0))   # ~17 (log2 100k)

Типичный вывод:

star BFS max queue: 99999
star DFS max stack: 99999
path BFS max queue: 1
path DFS max stack: 99999
tree BFS max queue: 25000
tree DFS max stack: 17

Интересные выводы:

• Звезда — оба алгоритма потребляют O(V). У DFS stack тоже большой, потому что мы все рёбра добавляем в stack одним махом до извлечения. Это не «глубина», это «накопленные неоткрытые вершины».
• Верёвка — DFS забирает в V раз больше памяти. Это плохо.
• Сбалансированное дерево — DFS даёт логарифмический stack, BFS — линейный фронт. DFS в 1500 раз компактнее.

Когда BFS лучше по памяти

Когда граф длинный, но узкий. Глубина большая, ширина маленькая. Linked-list-like структуры, long pipelines в lineage.

Когда граф очень широкий, но фронт «доходит» до листьев быстро. BFS успеет завершиться, не накапливая много.

Когда DFS лучше по памяти

Когда граф сбалансированный (логарифмическая глубина, экспоненциальная ширина). Это деревья. DFS — стандарт.

Когда граф широкий и неглубокий — DFS пройдёт быстро по линиям и сэкономит.

DE-кейсы: какой алгоритм выбрать

Глубина для рекурсивного DFS

Если вы используете рекурсивный DFS — учитывайте лимит стека Python (по умолчанию ~1000). На lineage с цепочками глубиной более 1000 — рекурсивный DFS упадёт. Варианты:

1. Итеративный DFS через явный list as stack. Безопасно для любой глубины (лимит — RAM).
2. sys.setrecursionlimit(N) — увеличить лимит. Рискованно: нативный стек C тоже имеет лимит (8 МБ на Linux, 1 МБ на Windows), при превышении — segfault Python-процесса.
3. BFS — обходит не рекурсивно, нет проблем с глубиной.

import sys
sys.setrecursionlimit(50000)   # рискованно, может упасть с segfault
# лучше использовать итеративный DFS

Размер vs скорость на больших графах

В терминах общего времени работы — они одинаковы (O(V+E)). Но на современных CPU есть нюанс: BFS «расширяется» одинаково во все стороны, DFS «идёт по одной линии». Это значит:

• BFS обращается к памяти в более случайном порядке (фронт распылён). Cache-misses чаще, но prefetcher успевает.
• DFS идёт по цепочке указателей вглубь. Прямо pointer-chasing, особенно на adjacency list.

На практике для типичных DE-графов (sparse, средняя длина цепочки 5-15) разница в скорости незначительная. Выбирайте по памяти и удобству задачи.

Альтернатива: bidirectional BFS

Если задача — «есть ли путь между s и t», иногда выгоднее запустить два BFS одновременно: один из s, второй из t (по обратным рёбрам). Они встречаются «где-то посередине». Если глубина пути h, то bidirectional BFS обходит в среднем O(b^(h/2)) против O(b^h) у простого BFS. На графах с большим branching factor — гигантская экономия. Используется в Дикстре, A*, и часто в задачах shortest path.

В DE применяется редко — обычно одного направления хватает. Но знать про существование полезно.

Попробуй сам

Сгенерируйте три графа по 100 000 вершин:

1. path graph — 0 -> 1 -> 2 -> … -> 99999.
2. balanced binary tree — каждая вершина имеет 2 ребёнка (или меньше), если возможно.
3. dense bushy graph — каждая вершина связана с 10 случайными.

Запустите BFS и DFS из вершины 0, измерьте максимальный размер queue/stack во время обхода.

Ожидаемое:

• path: BFS queue ~1, DFS stack ~100k,
• tree: BFS queue ~50k, DFS stack ~17,
• bushy: BFS queue ~50k-100k, DFS stack — нестабилен, обычно похож на BFS.

Вывод: на длинных «verevka»-графах выбирайте BFS (или итеративный DFS). На сбалансированных tree-графах — DFS.

В следующем уроке вернёмся к BFS как к инструменту поиска shortest path, и поговорим о пограничном случае — weighted graph и почему BFS там не работает (без полного разбора Dijkstra).