Обходы графов: BFS, DFS, топологическая сортировка, компоненты

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

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

Эта статья опирается на понятия сложности и инвариантов из Анализа алгоритмов и на понимание рекурсии из Рекурсии и разделяй-и-властвуй.

Словарь: что именно мы обходим

Граф G = (V, E): множество вершин и множество рёбер. Дальше по тексту n = |V|, m = |E|.

• Ориентированный: ребро u → v не даёт права идти v → u. Зависимости, ссылки, переходы состояний — почти всегда ориентированные. Неориентированный: ребро — симметричное отношение (дружба, физическая связность).
• Взвешенный: у ребра есть стоимость. Обходы в этой статье весов не знают — они появятся в Кратчайших путях.
• Плотность: m может быть от n − 1 (дерево) до n² (полный граф). Реальные графы почти всегда разрежены: m = O(n) или O(n log n) — ключевой факт для выбора представления.
• DAG (directed acyclic graph) — ориентированный граф без циклов; главный герой раздела про топологическую сортировку.

Сумма степеней в неориентированном графе равна 2m, сумма indeg (как и сумма outdeg) в ориентированном равна m. Отсюда сразу следует главное: обход, проходящий по каждому ребру константное число раз, стоит O(n + m) — не O(n · m) и не O(m log m). Это и называется «линейное время для графов».

Как хранить граф: три представления и одно правильное

Матрица смежности

Двумерный массив A[u][v] ∈ {0, 1}.

• Проверка «есть ли ребро u–v» — O(1).
• Перебор соседей вершины — O(n) всегда, даже если сосед один.
• Память — Θ(n²) бит. Для n = 100 000 это 1.25 ГБ даже в битовой упаковке.

Матрица оправдана на маленьких плотных графах (n ≤ 2000), в алгоритмах вроде Флойда–Уоршелла и там, где нужен именно быстрый предикат «смежны ли». Для обходов она почти всегда неправильный выбор: BFS по матрице стоит Θ(n²) независимо от числа рёбер.

Список смежности

Для каждой вершины — список её соседей. Память Θ(n + m), перебор соседей — по факту. Это дефолт.

Строится тривиально: adj = [[] for _ in range(n)], затем adj[u].append(v) на каждое ребро (и симметрично adj[v].append(u), если граф неориентированный).

CSR: список смежности, который любит процессор

list[list[int]] в Python — это n отдельных объектов в куче: заголовки, указатели, непредсказуемые адреса. Каждый переход к соседям новой вершины — почти гарантированный промах кэша. Продакшн-библиотеки хранят граф в CSR (compressed sparse row): два плоских массива — start длины n + 1 и adj длины m (или 2m для неориентированного). Соседи вершины v — непрерывный срез adj[start[v] : start[v+1]].

def build_csr(n: int, edges: list[tuple[int, int]], directed: bool = False):
    """CSR через подсчёт степеней и префиксные суммы. O(n + m), два прохода."""
    deg = [0] * n
    for u, v in edges:
        deg[u] += 1
        if not directed:
            deg[v] += 1

    start = [0] * (n + 1)
    for v in range(n):                     # префиксные суммы степеней
        start[v + 1] = start[v] + deg[v]

    pos = start[:n]                        # курсор записи для каждой вершины
    adj = [0] * start[n]
    for u, v in edges:
        adj[pos[u]] = v
        pos[u] += 1
        if not directed:
            adj[pos[v]] = u
            pos[v] += 1
    return start, adj

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

Типичная ошибка: хранить граф как dict[str, list[str]] с именами-строками в горячем цикле. Хеширование строк на каждом ребре легко съедает больше времени, чем сам алгоритм. Заведите словарь «имя → целочисленный id» один раз на входе, работайте с числами, а имена верните только на выводе.

Один каркас, два порядка

Все обходы — это одна процедура с одним параметром: чем является «мешок» ожидающих вершин.

• Мешок — очередь FIFO ⇒ получаем BFS: вершины выходят в порядке неубывания расстояния от старта.
• Мешок — стек LIFO ⇒ получаем DFS: обход уходит вглубь, пока может.
• Мешок — приоритетная очередь по накопленной стоимости ⇒ получаем Дейкстру (следующая статья).
• Мешок — приоритетная очередь по стоимости ребра ⇒ получаем Прима (Остовные деревья).

Это не поэтическая аналогия, а буквально один и тот же код. Полезно держать в голове именно так: вы не учите пять алгоритмов, вы учите один каркас и пять политик выбора.

Критически важная деталь каркаса: пометка ставится в момент помещения в мешок, а не в момент извлечения. Если пометить при извлечении, вершина может попасть в мешок много раз (по одному разу на каждое входящее ребро) — алгоритм останется корректным, но очередь раздуется до O(m), а в некоторых формулировках сложность деградирует. Это ошибка №1 в самописных BFS.

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

Интуиция

Бросьте камень в воду. Волна расходится кругами: сначала все точки на расстоянии 1, потом все на расстоянии 2, и никогда точка расстояния 3 не будет достигнута раньше точки расстояния 2. BFS — это ровно волна, а очередь FIFO — механизм, который гарантирует, что слой d + 1 начнёт обрабатываться только после того, как слой d полностью прочитан.

Реализация

from collections import deque

def bfs(adj: list[list[int]], s: int):
    """Расстояния в рёбрах и дерево кратчайших путей от s.
    Время O(n + m), память O(n)."""
    n = len(adj)
    dist = [-1] * n            # -1 = не обнаружена
    parent = [-1] * n
    dist[s] = 0
    q = deque([s])

    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == -1:          # ключ: помечаем при постановке в очередь
                dist[v] = dist[u] + 1
                parent[v] = u
                q.append(v)
    return dist, parent


def restore_path(parent: list[int], s: int, t: int) -> list[int]:
    """Путь s -> t по массиву предков. O(длины пути)."""
    if s != t and parent[t] == -1:
        return []                       # t недостижима
    path = []
    v = t
    while v != -1:
        path.append(v)
        v = parent[v]
    path.reverse()
    return path

Почему это правда даёт кратчайшие пути

Инвариант: в любой момент очередь содержит вершины не более чем двух соседних значений dist, и они идут неубывающим порядком — сначала все с d, потом все с d + 1.

Доказательство по индукции. База: в очереди только s с dist = 0. Шаг: пусть инвариант верен и мы извлекли u с dist[u] = d (по инварианту d — минимальное значение в очереди). Все новые вершины получают dist = d + 1 и уходят в хвост, где уже стоят только вершины со значениями d и d + 1. Порядок и двухзначность сохраняются.

Отсюда корректность: если dist[v] присвоено значение d + 1, то существует путь длины d + 1, а пути короче нет — иначе v был бы обнаружен при обработке слоя меньшего номера, потому что все вершины слоёв < d уже полностью обработаны к этому моменту.

Сложность. Каждая вершина ставится в очередь ровно один раз (dist[v] == -1 проверяется до вставки), каждый список смежности перебирается ровно один раз ⇒ Θ(n + m) времени. Память: O(n) на dist/parent плюс очередь. Пик очереди — это ширина графа, максимальный размер слоя; на графе «звезда» это n − 1, на длинной цепочке — 1. На социальных графах ширина огромна: BFS по Facebook-графу упирается в память очереди, а не во время.

Варианты, которые закрывают половину задач

Многоисточниковый BFS. Нужно расстояние до ближайшего из множества источников (ближайший склад, ближайший заражённый узел, ближайшая стена)? Не запускайте BFS k раз — это O(k(n + m)). Положите в очередь все источники сразу с dist = 0: код тот же, меняется только инициализация, сложность остаётся O(n + m). Формально это обычный BFS на графе с добавленным виртуальным суперисточником, соединённым нулевыми рёбрами со всеми источниками.

0-1 BFS. Если веса рёбер только 0 и 1, полноценная Дейкстра с кучей избыточна. Двусторонняя очередь: ребро веса 0 — appendleft, веса 1 — append. Инвариант двухзначности сохраняется, сложность остаётся O(n + m) вместо O(m log n).

def bfs_01(adj: list[list[tuple[int, int]]], s: int) -> list[float]:
    """adj[u] = [(v, w)], w in {0, 1}. O(n + m)."""
    INF = float("inf")
    dist = [INF] * len(adj)
    dist[s] = 0
    dq = deque([s])
    while dq:
        u = dq.popleft()
        for v, w in adj[u]:
            nd = dist[u] + w
            if nd < dist[v]:
                dist[v] = nd
                dq.appendleft(v) if w == 0 else dq.append(v)
    return dist

Классический прикладной случай — сетка, где движение по коридору бесплатно, а «пробить стену»/«сменить направление» стоит 1.

BFS по неявному графу. Граф не обязан существовать в памяти. Вершина — состояние (позиция фишек, набор посещённых городов, содержимое регистров), рёбра — допустимые ходы, порождаемые функцией. Так решаются кубик Рубика, «пятнашки», поиск минимального числа операций. Список смежности заменяется генератором, dist — словарём или хеш-множеством. Ограничение — экспоненциальный рост слоёв; отсюда двунаправленный BFS (волна из старта и из финиша навстречу, O(b^{d/2}) вместо O(b^d)) и переход к A* (Кратчайшие пути).

Проверка двудольности. Тот же BFS, но вместо dist ведём color[v] = color[u] ^ 1. Если встретилось ребро в вершину того же цвета — граф не двудолен: нашёлся цикл нечётной длины. Обратное тоже верно (граф двудолен ⟺ нет нечётных циклов), так что BFS-раскраска — полный критерий, а не эвристика. Не забудьте внешний цикл по всем стартам: двудольность проверяется покомпонентно.

Уровневый BFS и почему он важен для прода

Если переписать BFS не через одну очередь, а через два массива «текущий фронт» и «следующий фронт», алгоритм становится тривиально параллелизуемым: обработка всего фронта независима. Именно эта форма лежит в основе BFS на GPU, в Pregel/Giraph и в direction-optimizing BFS.

// Уровневый BFS по CSR: dist инициализирован -1, dist[src] = 0.
// frontier и next — переиспользуемые буферы, аллокаций внутри цикла нет.
for d := int32(1); len(frontier) > 0; d++ {
    next = next[:0]
    for _, u := range frontier {
        // соседи лежат подряд: последовательное чтение, работает предвыборка
        for _, v := range adj[start[u]:start[u+1]] {
            if dist[v] < 0 {
                dist[v] = d
                next = append(next, v)
            }
        }
    }
    frontier, next = next, frontier // swap буферов
}

(Синтаксис Go разбирается в треке Go.)

Beamer, Asanović и Patterson показали, что на графах с малым диаметром и огромным средним фронтом выгодно на «толстых» слоях переворачивать направление: не «для каждой вершины фронта перебрать её соседей» (top-down), а «для каждой непосещённой вершины проверить, нет ли у неё соседа во фронте» (bottom-up) — и остановиться на первом же. Гибрид даёт 3–7× ускорения на социальных графах (SC'12, PDF).

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

Интуиция и времена входа/выхода

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

Теорема о скобках. Для любых u, v интервалы [tin[u], tout[u]] и [tin[v], tout[v]] либо не пересекаются, либо один целиком вложен в другой. Вложенность означает, что одна вершина — потомок другой в дереве DFS.

Это единственная теорема, которую нужно запомнить про DFS: из неё выводятся почти все дальнейшие алгоритмы — топологическая сортировка, SCC, мосты, точки сочленения, детект циклов, LCA через эйлеров обход.

Три цвета и классификация рёбер

Для ориентированного графа ребро u → v при u серой классифицируется по цвету v:

В неориентированном графе прямых и поперечных рёбер не бывает вовсе — только древесные и обратные. Это тоже следствие теоремы о скобках, и именно поэтому проверка цикла в неориентированном графе так проста.

Итеративный DFS: как писать, чтобы не переполнить стек

Рекурсивный DFS — три строки, и на графе с длинной цепочкой из 100 000 вершин он падает: дефолтный sys.getrecursionlimit() в CPython равен 1000, JVM отдаёт StackOverflowError на нескольких десятках тысяч кадров. В проде DFS пишут итеративно. Наивная версия «запихнуть всех соседей в стек» не эквивалентна рекурсии: она не даёт корректных tout и раздувает стек до O(m). Правильный приём — хранить на стеке итератор по соседям, то есть буквально воспроизвести кадр рекурсии.

def dfs_iterative(adj: list[list[int]], s: int, tin: list[int], tout: list[int], timer: int) -> int:
    """Итеративный DFS с корректными tin/tout. O(n + m) времени, O(n) памяти на стек."""
    tin[s] = timer
    timer += 1
    stack = [(s, iter(adj[s]))]          # кадр = (вершина, курсор по её соседям)

    while stack:
        u, it = stack[-1]
        for v in it:                     # итератор общий с кадром: продолжаем с места остановки
            if tin[v] == -1:
                tin[v] = timer
                timer += 1
                stack.append((v, iter(adj[v])))
                break                    # «рекурсивный вызов»
        else:                            # соседи кончились -> «возврат из вызова»
            tout[u] = timer
            timer += 1
            stack.pop()
    return timer


def dfs_all(adj: list[list[int]]):
    """Полный обход леса DFS для возможно несвязного графа."""
    n = len(adj)
    tin, tout = [-1] * n, [-1] * n
    timer = 0
    for s in range(n):
        if tin[s] == -1:
            timer = dfs_iterative(adj, s, tin, tout, timer)
    return tin, tout

Конструкция for ... else здесь — не украшение: ветка else выполняется ровно тогда, когда цикл завершился без break, то есть когда соседи исчерпаны. Это точное соответствие «возврату из функции».

Обнаружение цикла

WHITE, GRAY, BLACK = 0, 1, 2

def find_cycle_directed(adj: list[list[int]]) -> list[int] | None:
    """Возвращает вершины цикла или None. O(n + m)."""
    n = len(adj)
    color = [WHITE] * n
    parent = [-1] * n

    for s in range(n):
        if color[s] != WHITE:
            continue
        stack = [(s, iter(adj[s]))]
        color[s] = GRAY
        while stack:
            u, it = stack[-1]
            for v in it:
                if color[v] == GRAY:                 # обратное ребро -> цикл
                    cycle = [v]
                    x = u
                    while x != v:
                        cycle.append(x)
                        x = parent[x]
                    cycle.append(v)
                    cycle.reverse()
                    return cycle
                if color[v] == WHITE:
                    color[v] = GRAY
                    parent[v] = u
                    stack.append((v, iter(adj[v])))
                    break
            else:
                color[u] = BLACK
                stack.pop()
    return None

Типичная ошибка: считать циклом любое ребро в уже посещённую вершину. В ориентированном графе 1 → 2, 1 → 3, 2 → 3 цикла нет, но при двухцветной логике «посещена / нет» ребро 2 → 3 будет ошибочно объявлено циклом. Нужны именно три цвета — то есть различать «на текущем пути» и «уже полностью обработана».

Топологическая сортировка

Определение. Топологический порядок ориентированного графа — такая нумерация вершин, что каждое ребро u → v идёт слева направо. Иначе говоря, «сначала зависимости, потом зависящее».

Теорема. Топологический порядок существует ⟺ граф ациклический (DAG). Необходимость очевидна: цикл невозможно вытянуть в линию. Достаточность конструктивна — оба алгоритма ниже её доказывают.

Типичный DAG, который вы видите каждый день:

Порядок сборки — это топологическая сортировка этого графа. Параллельная сборка make -j — это тот же порядок, но с учётом того, что вершины одного «уровня» независимы.

Алгоритм Кана: снятие слоёв нулевой степени

Идея прямая как палка: если у вершины нет входящих рёбер, её можно поставить первой. Ставим, удаляем, повторяем.

def topo_kahn(adj: list[list[int]]) -> list[int]:
    """Топологический порядок или исключение при цикле. O(n + m)."""
    n = len(adj)
    indeg = [0] * n
    for u in range(n):
        for v in adj[u]:
            indeg[v] += 1

    q = deque(u for u in range(n) if indeg[u] == 0)
    order: list[int] = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)

    if len(order) != n:
        stuck = [v for v in range(n) if indeg[v] > 0]
        raise ValueError(f"граф содержит цикл; застряли на {len(stuck)} вершинах: {stuck[:10]}")
    return order

Три бонуса алгоритма Кана, за которые его любят в проде:

1. Диагностика цикла бесплатна. Если результат короче n, оставшиеся вершины — ровно те, что лежат на циклах или достижимы из них. Дальше можно запустить find_cycle_directed на индуцированном подграфе и показать пользователю конкретную цепочку A → B → C → A.
2. Уровни параллелизма. Если извлекать не по одной вершине, а весь текущий фронт целиком, получаются слои: вершины одного слоя можно собирать/выполнять параллельно. Число слоёв — критический путь DAG, нижняя граница времени при любом числе воркеров.
3. Детерминизм по требованию. Заменив deque на heapq, получаем лексикографически минимальный топологический порядок за O(n log n + m). Это то, чем добиваются воспроизводимых сборок и стабильных диффов в lock-файлах.

Через DFS: обратный порядок выхода

Теорема. В DAG обратный порядок значений tout (reverse postorder) — топологический.

Доказательство. Рассмотрим ребро u → v. Если в момент обработки ребра v белая, DFS входит в неё немедленно, значит tout[v] < tout[u]. Если v чёрная — она уже завершена, и снова tout[v] < tout[u]. Серой v быть не может: это обратное ребро, то есть цикл, а граф ациклический. Значит для любого ребра tout[u] > tout[v], и сортировка по убыванию tout даёт топологический порядок. ∎

Код здесь уже написан: это find_cycle_directed из предыдущего раздела, в котором нужно дописать order.append(u) рядом с color[u] = BLACK, а в конце сделать order.reverse(). Обнаружение цикла и топосортировка — один и тот же обход, отличающийся тремя строками. Заодно из этого видно, почему tout так ценны: обратный постпорядок — это «бесплатный» побочный продукт любого DFS.

Кан против DFS: сложность одинаковая, O(n + m). Кан удобнее, когда нужны уровни параллелизма и понятная диагностика; DFS-версия удобнее, когда tout всё равно нужны для чего-то ещё (SCC), и когда граф задан лениво — вы не можете посчитать indeg, не обойдя весь граф.

Что даёт топологический порядок дальше

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

def longest_path_dag(adj: list[list[int]], order: list[int]) -> list[int]:
    """Длиннейший путь в рёбрах = критический путь проекта. O(n + m)."""
    dp = [0] * len(adj)
    for u in order:                      # все предшественники u уже посчитаны
        for v in adj[u]:
            dp[v] = max(dp[v], dp[u] + 1)
    return dp

Заметьте контраст: длиннейший путь в произвольном графе — NP-трудная задача (NP-полнота), а в DAG — линейная. Вся разница в существовании топологического порядка.

Компоненты

Связные компоненты неориентированного графа

Простейшее применение обхода: запускаем BFS/DFS из каждой непосещённой вершины, номер запуска и есть номер компоненты.

def connected_components(adj: list[list[int]]) -> tuple[int, list[int]]:
    """Возвращает (число компонент, comp[v]). O(n + m) времени, O(n) памяти."""
    n = len(adj)
    comp = [-1] * n
    c = 0
    for s in range(n):
        if comp[s] != -1:
            continue
        comp[s] = c
        stack = [s]
        while stack:
            u = stack.pop()
            for v in adj[u]:
                if comp[v] == -1:
                    comp[v] = c
                    stack.append(v)
        c += 1
    return c, comp

Альтернатива — система непересекающихся множеств (DSU / union-find): для каждого ребра объединяем концы, компонента — корень. Оба варианта линейны на практике, но выбор не произволен:

• Обход требует уже построенного списка смежности и даёт заодно дерево обхода, расстояния, порядок. Работает только когда граф целиком доступен.
• DSU обрабатывает рёбра потоком, в любом порядке, не храня граф вообще: память O(n) независимо от m. Незаменим, когда рёбра приходят из файла/стрима или когда структура нужна инкрементально (алгоритм Краскала, Остовные деревья).
• DSU не умеет удалять рёбра. Если связность нужна при удалениях — обходы или специализированные динамические структуры.

Мосты и точки сочленения: где сеть хрупкая

Мост — ребро, удаление которого увеличивает число компонент. Точка сочленения (articulation point) — вершина с тем же свойством. Прикладной смысл прямой: единственная точка отказа в сети, критический сервис, чьё падение разрывает кластер надвое.

Алгоритм Тарьяна строится на величине low[v] — минимальном tin, достижимом из поддерева v по древесным рёбрам плюс не более одного обратного ребра.

• Ребро (u, v) — мост ⟺ low[v] > tin[u]: из поддерева v нет ни одного обратного ребра, обходящего это ребро.
• Не-корневая вершина u — точка сочленения ⟺ у неё есть ребёнок v с low[v] >= tin[u].
• Корень DFS — точка сочленения ⟺ у него в дереве DFS два или более ребёнка.

import sys

def bridges(n: int, adj: list[list[tuple[int, int]]]) -> list[int]:
    """adj[u] = [(v, edge_id)]. Возвращает id рёбер-мостов. O(n + m).
    Хранение id ребра, а не вершины-родителя, корректно обрабатывает кратные рёбра:
    два параллельных ребра между u и v мостами не являются."""
    sys.setrecursionlimit(max(10000, 4 * n))     # на больших графах — переписать итеративно
    tin = [-1] * n
    low = [0] * n
    timer = 0
    result: list[int] = []

    def dfs(u: int, parent_edge: int) -> None:
        nonlocal timer
        tin[u] = low[u] = timer
        timer += 1
        for v, eid in adj[u]:
            if eid == parent_edge:
                continue                          # не идём назад по тому же ребру
            if tin[v] != -1:
                low[u] = min(low[u], tin[v])      # обратное ребро: берём tin, НЕ low
            else:
                dfs(v, eid)
                low[u] = min(low[u], low[v])
                if low[v] > tin[u]:
                    result.append(eid)

    for s in range(n):
        if tin[s] == -1:
            dfs(s, -1)
    return result

Две частые ошибки здесь. Первая — писать low[u] = min(low[u], low[v]) для обратного ребра: по обратному ребру нужно брать именно tin[v], иначе через поперечные связи «просачивается» лишняя информация и мосты теряются. Вторая — пропускать родителя по номеру вершины (if v == parent: continue): на графе с двумя параллельными рёбрами между u и v это ошибочно объявит их мостами.

Сильно связные компоненты (SCC)

В ориентированном графе «связность» распадается на два понятия. Сильно связная компонента — максимальное множество вершин, в котором из любой достижима любая. Если стянуть каждую SCC в одну вершину, получится конденсация — и она всегда DAG. Это мощный приём: любую задачу на произвольном орграфе можно свести к задаче на DAG плюс задаче внутри компонент.

def kosaraju(adj: list[list[int]]) -> tuple[int, list[int]]:
    """Число SCC и comp[v]. Компоненты пронумерованы в топологическом порядке
    конденсации: если есть ребро из SCC a в SCC b, то comp_id(a) < comp_id(b).
    O(n + m) времени, O(n + m) памяти (нужен транспонированный граф)."""
    n = len(adj)
    radj: list[list[int]] = [[] for _ in range(n)]
    for u in range(n):
        for v in adj[u]:
            radj[v].append(u)

    # Проход 1: postorder в исходном графе, итеративно.
    visited = [False] * n
    order: list[int] = []
    for s in range(n):
        if visited[s]:
            continue
        visited[s] = True
        stack = [(s, iter(adj[s]))]
        while stack:
            u, it = stack[-1]
            for v in it:
                if not visited[v]:
                    visited[v] = True
                    stack.append((v, iter(adj[v])))
                    break
            else:
                order.append(u)
                stack.pop()

    # Проход 2: DFS по обратному графу в порядке убывания времени выхода.
    comp = [-1] * n
    c = 0
    for s in reversed(order):
        if comp[s] != -1:
            continue
        comp[s] = c
        stack = [s]
        while stack:
            u = stack.pop()
            for v in radj[u]:
                if comp[v] == -1:
                    comp[v] = c
                    stack.append(v)
        c += 1
    return c, comp

Почему это работает. Вершина с максимальным tout во всём графе всегда лежит в «истоковой» SCC конденсации. В транспонированном графе истоковая компонента становится стоковой — DFS из неё не может выйти за пределы своей SCC. Поэтому каждый запуск второго прохода выгребает ровно одну компоненту. Строгое изложение — CLRS, глава об элементарных алгоритмах на графах.

Косарайю против Тарьяна. Косарайю — два обхода и явный транспонированный граф: проще объяснить, проще отладить, но 2× работы и 2× памяти на рёбра. Алгоритм Тарьяна (SIAM J. Comput., 1972) находит SCC за один проход через low-значения и стек компонент — быстрее на практике и не требует Gᵀ, что принципиально, если граф не помещается в память дважды. Оба O(n + m).

Прикладные SCC: детект циклических зависимостей между модулями (и «схлопывание» их в один компонент сборки), поиск взаимных блокировок в графе ожидания транзакций (deadlock — это цикл, то есть нетривиальная SCC), 2-SAT за линейное время (Aspvall–Plass–Tarjan, 1979), сжатие графа веб-страниц перед PageRank, анализ графа вызовов в компиляторах: LLVM обрабатывает функции по SCC графа вызовов, чтобы корректно работать со взаимной рекурсией.

Карта задач: что и каким обходом решается

Сложность: сводка

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

Типичные ошибки

1. Пометка при извлечении, а не при вставке. Очередь раздувается до O(m), а на больших графах это разница между «работает» и «OOM».
2. Две метки вместо трёх цветов при поиске цикла в орграфе — ложные срабатывания на прямых и поперечных рёбрах.
3. Рекурсивный DFS в проде. Цепочка длиной 50 000 вершин — вполне реальный граф зависимостей монорепозитория, и RecursionError там прилетает в самый неудачный момент. Итеративная версия с итератором на стеке решает вопрос навсегда.
4. Наивный «итеративный DFS» (stack.extend(adj[u])) не даёт корректных tout и потому непригоден для топосортировки, SCC и мостов.
5. Обход только из вершины 0 при несвязном графе. Всегда пишите внешний цикл for s in range(n), кроме случаев, когда связность гарантирована.
6. BFS по матрице смежности — Θ(n²) вместо Θ(n + m), незаметно, пока граф мал.
7. Пропуск родителя по вершине, а не по ребру в поиске мостов — кратные рёбра ломают ответ.
8. low[u] = min(low[u], low[v]) по обратному ребру вместо tin[v]. Классическая опечатка, дающая правильный ответ на большинстве тестов и неправильный на некоторых.
9. Реконструкция пути без проверки достижимости: цикл while v != -1 по массиву parent, заполненному -1, вернёт бессмысленный путь из одной вершины вместо «пути нет».
10. Изменение графа во время обхода или разрушение входных данных алгоритмом (Кан, «съедающий» рёбра): либо исключение при итерации, либо неверный результат при повторном вызове.

Как это выглядит в проде

• Системы сборки. Make, Ninja, Bazel строят DAG целей и топологически его сортируют; -j N — это исполнение слоёв Кана пулом воркеров, а сообщение о циклической зависимости — тот самый случай len(order) != n. См. глоссарий Bazel.
• Инфраструктура как код. Terraform строит граф ресурсов и обходит его; terraform graph буквально выводит этот DAG (документация).
• Оркестраторы задач. Airflow: DAG — центральное понятие модели, планировщик выпускает таски, у которых все апстримы завершены — это Кан в чистом виде (docs).
• Пакетные менеджеры. Разрешение зависимостей — топосортировка плюс детект циклов; сообщение «circular dependency A → B → A» получается ровно алгоритмом из раздела про поиск цикла.
• Сборка мусора. Фаза mark в трассирующих GC — обход графа объектов от корней с явным стеком (рекурсия недопустима: глубина не ограничена), а «трёхцветная маркировка» конкурентных GC — та же схема белая/серая/чёрная, что и в DFS выше. Kubernetes собирает объекты по ownerReferences тем же принципом (docs).
• Электронные таблицы и реактивные системы. Пересчёт после изменения ячейки — обход в топологическом порядке графа формул; циклическая ссылка — обнаруженный цикл.
• Git и компиляторы. История коммитов — DAG (git rev-list --topo-order, merge-base); в компиляторах — SCC графа вызовов для взаимной рекурсии и обратный постпорядок как порядок итераций dataflow-анализа.
• Социальные графы. «Шесть рукопожатий» — двунаправленный BFS; «друзья друзей» — BFS глубины 2 с ограничением ветвления.

Когда граф перестаёт помещаться в память, обходы не исчезают, а меняют форму: появляются внешнепамятные и потоковые варианты (Потоковые алгоритмы) и модели вычислений вида BSP/Pregel, где уровневый BFS становится последовательностью суперштагов с обменом сообщениями (Параллельные и распределённые алгоритмы). Стандартный полигон для замеров здесь — GAP Benchmark Suite, где BFS и SCC входят в базовый набор ядер.

Источники

• CLRS, Introduction to Algorithms, 4-е изд. — главы об элементарных алгоритмах на графах: BFS, DFS, теорема о скобках, топосортировка, SCC с полными доказательствами. mitpress.mit.edu
• Sedgewick & Wayne, Algorithms, 4-е изд., глава 4 — отличные визуализации и реализации на Java. algs4.cs.princeton.edu/40graphs
• R. Tarjan, Depth-First Search and Linear Graph Algorithms, SIAM J. Comput., 1972 — первоисточник SCC, мостов и точек сочленения. doi:10.1137/0201010
• A. B. Kahn, Topological sorting of large networks, CACM, 1962. doi:10.1145/368996.369025
• Beamer, Asanović, Patterson, Direction-Optimizing Breadth-First Search, SC'12. PDF
• Malewicz et al., Pregel: A System for Large-Scale Graph Processing, SIGMOD 2010. doi:10.1145/1807167.1807184
• cp-algorithms — компактные разборы с кодом: BFS, мосты, SCC.
• NetworkX (docs) и Boost Graph Library (docs) — референсные реализации и промышленный API обходов через визиторы.

Итог

Обходы — самый выгодный по соотношению «усилие / охват задач» кусок алгоритмической подготовки. Что нужно унести:

1. Один каркас, разные мешки. FIFO → BFS, LIFO → DFS, приоритетная очередь → Дейкстра и Прим. Это буквально один алгоритм.
2. Всё линейно, Θ(n + m). Если ваш обход медленнее — вы либо взяли матрицу смежности, либо кладёте вершины в мешок больше одного раза.
3. BFS даёт расстояния, DFS даёт структуру. tin/tout и теорема о скобках — фундамент топосортировки, SCC, мостов и точек сочленения.
4. Три цвета, не две метки; пометка при вставке, не при извлечении; DFS итеративный, с итератором на стеке. Три правила, закрывающие большинство багов.
5. Топологический порядок превращает орграф в линию, а линия превращает NP-трудные задачи (длиннейший путь) в один цикл for. SCC + конденсация сводят к DAG любой орграф: сначала схлопнуть циклы, потом работать с DAG.
6. Представление важнее, чем кажется. CSR против списка списков — разы на реальных объёмах при одной и той же асимптотике.

Чек-лист перед тем, как писать обход: граф ориентированный? связный? нужны расстояния или структура? граф статический (CSR) или растёт (списки)? какая глубина возможна? нужна ли диагностика цикла для пользователя? Ответы на эти шесть вопросов однозначно определяют реализацию.

Что дальше

Обходы игнорируют веса — они считают все рёбра одинаковыми. Как только у ребра появляется стоимость (километры, миллисекунды, деньги, вероятность), FIFO-очередь перестаёт давать оптимум и её место занимает приоритетная очередь, а вместе с ней — целое семейство алгоритмов с разными допущениями об отрицательных весах, плотности графа и наличии эвристики: Кратчайшие пути: Дейкстра, Беллман–Форд, Флойд–Уоршелл, A*.