Рекурсия или явный стек, и чем отличается обход в ширину

Если ты умеешь писать обход в глубину на явном стеке (включая вариант с индексом соседа), знаешь предел глубины рекурсии и понимаешь, чем обход в ширину отличается по результату и по памяти, листай до «Теперь сам».

Как думаешь, на каком графе упадёт рекурсия

Граф - простая цепочка: 0→1→2→...→N. Прежде чем читать дальше, прикинь, при каком N рекурсивный обход перестанет работать в Python и при каком - в программе на C++ с восьмимегабайтным стеком. Подсказка: кадр вызова занимает десятки-сотни байт, а Python по умолчанию ограничивает глубину явно.

На что это похоже

Разница между тем, чтобы держать маршрут в голове, и тем, чтобы записывать его на бумаге. Пока вложенность небольшая, голова справляется. Но если надо запомнить миллион поворотов, голова кончится - а блокнот нет, у него другой предел. Переписывание рекурсии на явный стек - это ровно перенос маршрута из «головы» (системного стека вызовов) в «блокнот» (обычный массив в куче).

Механизм: три способа обойти один граф

# 1) рекурсия: коротко, но глубина ограничена системой
def dfs(v):
    visited[v] = True
    for u in adj[v]:
        if not visited[u]:
            dfs(u)

# 2) явный стек, простой вариант: тот же охват, другой порядок
def dfs_iter(start):
    stack = [start]
    while stack:
        v = stack.pop()
        if visited[v]:          # вершина могла попасть в стек дважды
            continue
        visited[v] = True
        for u in adj[v]:
            if not visited[u]:
                stack.append(u)

# 3) явный стек с индексом соседа: ТОЧНАЯ копия рекурсии, есть вход и выход
def dfs_exact(start):
    stack = [(start, 0)]
    visited[start] = True
    tin[start] = tick()
    while stack:
        v, i = stack[-1]
        if i < len(adj[v]):
            stack[-1] = (v, i + 1)      # сдвинули «указатель соседа»
            u = adj[v][i]
            if not visited[u]:
                visited[u] = True
                tin[u] = tick()
                stack.append((u, 0))
        else:
            tout[v] = tick()            # соседи кончились - это ВЫХОД из вершины
            stack.pop()

Второй вариант проще, но у него две особенности. Во-первых, соседи выкладываются в стек и достаются в обратном порядке - обход пойдёт «зеркально» рекурсии. Во-вторых, одна вершина может попасть в стек несколько раз (её положили из разных соседей до того, как посетили), поэтому нужна проверка при извлечении; иначе на плотном графе стек раздуется до O(E).

Третий вариант нужен там, где важны tin/tout или действие «при выходе» - а это все алгоритмы следующих глав: топологическая сортировка, компоненты сильной связности, мосты.

Замена стека на очередь превращает обход в глубину в обход в ширину:

from collections import deque
def bfs(start):
    dist = [-1] * V
    dist[start] = 0
    q = deque([start])
    while q:
        v = q.popleft()                 # единственное отличие: берём из НАЧАЛА
        for u in adj[v]:
            if dist[u] == -1:
                dist[u] = dist[v] + 1
                q.append(u)
    return dist

Правило

Глубина рекурсивного обхода доходит до V: в Python предел около тысячи вызовов, в компилируемых языках - сотни тысяч, поэтому на больших графах обход переписывают на явный стек. Простой вариант («сложить соседей») даёт другой порядок и требует проверки посещённости при извлечении; точная копия рекурсии хранит на стеке пару «вершина + индекс соседа» и умеет отличать вход от ВЫХОДА. Стек, заменённый очередью, даёт обход в ширину: он посещает вершины по уровням и находит кратчайшие пути в невзвешенном графе за O(V + E). Память: в глубину - O(длины пути), в ширину - O(ширины уровня).

Разбор: где кончается рекурсия

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

В компилируемых языках считают иначе. Стек потока по умолчанию - около 8 МБ, кадр обхода занимает порядка 50-100 байт (адрес возврата, локальные переменные, выравнивание). Делим: 8·10⁶ / 80 ≈ 100 000 вложенных вызовов. То есть цепочка из ста тысяч вершин - уже граница, а из миллиона - гарантированное падение.

И теперь главное: цепочка - не экзотика. Длинный путь получается на дорожной сети (шоссе), в графе зависимостей с длинной цепочкой включений, на сетке-лабиринте со змейкой из коридоров, в дереве каталогов с глубокой вложенностью. Поэтому правило простое: разовый скрипт - можно рекурсию; код, который увидит чужие данные, - явный стек.

Разбор: одинаковый охват, разный порядок и разный ответ

Граф: 0-1, 0-2, 1-3, 2-3, стартуем из 0.

Обход в ГЛУБИНУ (рекурсия, соседи по возрастанию): 0 → 1 → 3 → 2. Расстояния, если их считать как длину пройденного пути: до 1 - один шаг, до 3 - два, до 2 - ТРИ (пришли через 1 и 3), хотя в графе есть прямое ребро 0-2.

Обход в ШИРИНУ: из 0 кладём в очередь 1 и 2 (уровень 1), потом из 1 кладём 3 (уровень 2), из 2 смотрим 3 - уже размечена. Расстояния: dist = [0, 1, 1, 2]. Это и есть КРАТЧАЙШИЕ расстояния в рёбрах, и обход в ширину даёт их всегда - потому что вершины выходят из очереди в порядке неубывания расстояния, а каждая размечается при первом же попадании.

Тот же пример объясняет и разницу в памяти. В глубину на стеке лежит текущий путь - на цепочке это V вершин, на широком «кусте» - всего пара. В ширину в очереди лежит целый уровень - на цепочке это одна вершина, а на графе, где у корня миллион соседей, это миллион. Ни один не лучше: выбирают по форме графа и по задаче.

Что ломается без этого

Первое: переписать рекурсию на стек, но помечать вершину только при извлечении и не проверять повторов - стек раздувается, а вершины обрабатываются по нескольку раз. Второе: ожидать от простого стекового варианта того же ПОРЯДКА, что у рекурсии: соседи достаются из стека с конца, поэтому порядок другой. Укладка соседей в обратном порядке совпадение чаще всего восстанавливает, но полагаться на это не стоит - вершина может попасть в стек несколько раз и всплыть не тогда, когда ждёшь; если порядок важен, бери вариант с индексом соседа. Третье: пытаться получить tout в простом варианте - его там нет, для этого нужен вариант с индексом соседа. Четвёртое: считать, что обход в ширину даёт кратчайшие пути во ВЗВЕШЕННОМ графе - нет, там нужен Дейкстра; обход в ширину работает, только когда все рёбра равноценны. Пятое: поднять лимит рекурсии в Python и считать вопрос закрытым - системный стек от этого не вырос, и падение станет менее понятным.

Зачем это в работе

Переполнение стека на рекурсивном обходе - классическая авария в продакшне: код работает год, пока кто-то не пришлёт данные с длинной цепочкой. Поэтому в библиотеках обходы почти всегда итеративные, и уметь их писать - часть ремесла. Обход в ширину нужен там, где важно «ближайшее»: кратчайший путь в клетках (игры, роботы), число рукопожатий в соцсети, поиск ближайшего работающего сервера в топологии, послойное распространение (заражение, рассылка), а также двунаправленный поиск - запуск обхода с обоих концов, который сокращает перебор на порядки. Приём «стек против очереди» стоит помнить и шире: одна и та же схема обхода с разным контейнером даёт разное поведение, и если заменить очередь на очередь с ПРИОРИТЕТАМИ, получится алгоритм Дейкстры - ровно об этом следующий раздел.

Теперь сам

Граф-звезда: центр 0 соединён с вершинами 1..999999 (миллион рёбер). И граф-цепочка: 0-1-2-...-999999. На каком из них упадёт рекурсивный обход в глубину, а на каком - обход в ширину по памяти? Сколько вершин будет лежать в стеке и в очереди в худший момент?