Графы: BFS, DFS и базовые задачи поиска и связности ТЕМА

О чём статья

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

В этой статье — компактный набор, который надо иметь в активном запасе: как представить граф в памяти, что такое BFS и DFS и в чём между ними разница (не только техническая, а смысловая), как искать компоненты связности двумя способами и когда какой удобнее. На каждый блок — задача-иллюстрация с разной сложностью и кодом на Python и C++.

---

Когда применять: сигналы в условии

• «Дороги», «связи», «друзья», «зависимости», «переходы». Любая попарная связь между объектами — это рёбра графа.
• «Кратчайшее расстояние при единичных рёбрах». BFS даёт кратчайший путь за $O(n + m)$, если все веса одинаковы.
• «Достижимость», «есть ли путь», «компоненты». Любой обход — BFS или DFS. На связных компонентах задача чаще сводится к подсчёту: сколько раз мы запускали обход из новой вершины.
• «Цикл», «топологическая сортировка», «двудольность». Чаще всего — DFS со специальной раскраской вершин.
• Сетка с препятствиями. Сетка $n \times m$ — это граф, где у каждой клетки до 4 соседей. Обход — BFS (для кратчайшего пути) или DFS (для компонент).

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

---

Представление графа

Перед обходом надо решить, как хранить граф. Два разумных способа:

Список смежности (adjacency list)

Для каждой вершины — список её соседей. На $n$ вершинах и $m$ рёбрах занимает $O(n + m)$ памяти. Это дефолт для олимпиадных задач: $n \le 10^5$, $m \le 2 \cdot 10^5$ — матрица не влезает, список — да.

adj[v] = [u1, u2, u3, ...]   # соседи v

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

Матрица смежности (adjacency matrix)

Двумерный массив g[v][u] = 1, если есть ребро. Память $O(n^2)$ — годится при $n \le 1000$, дальше — нет. Используется, когда нужны быстрые запросы «есть ли ребро между $v$ и $u$» за $O(1)$ или когда граф плотный ($m \sim n^2$, и список смежности не даёт выгоды).

Что выбираем по умолчанию

Список смежности. Матрицу — только если в условии явно $n \le 500$ и нужно много вершина-к-вершине проверок, или граф плотный. Все три задачи ниже — на списках смежности.

---

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

Идея в одну фразу

BFS поочерёдно раскрывает вершины уровнями расстояния от источника: сначала все на расстоянии 0, потом на расстоянии 1, потом 2 и так далее.

Псевдокод

dist[v] ← бесконечность для всех v
dist[s] ← 0
queue ← [s]
пока queue не пуст:
    v ← queue.pop_front()
    для каждого u из adj[v]:
        если dist[u] = бесконечность:
            dist[u] = dist[v] + 1
            queue.push_back(u)

Сложность: $O(n + m)$.

Почему это даёт кратчайшее расстояние

Инвариант BFS: вершины извлекаются из очереди в порядке неубывания dist. Когда мы впервые видим вершину $u$ (т.е. dist[u] ещё бесконечность), мы пришли в неё через ребро из соседа $v$, который уже посещён и имеет минимальное возможное dist[v]. Значит, dist[v] + 1 — это и есть минимальное расстояние до $u$. Доказывается индукцией по уровню.

Это работает только для единичных весов рёбер. Если веса разные — BFS заменяется на Дейкстру (с min-heap, $O((n + m) \log n)$) или на 0-1-BFS (с двусторонней очередью, $O(n + m)$), но это уже выходит за рамки статьи.

Базовый код BFS

---

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

Идея в одну фразу

DFS из вершины v сначала проваливается в первого непосещённого соседа u, рекурсивно обходит всё, что доступно из u, и только потом возвращается к остальным соседям v.

Псевдокод (рекурсивный)

visited[v] ← True
для каждого u из adj[v]:
    если не visited[u]:
        DFS(u)

Сложность: $O(n + m)$, $O(n)$ глубины стека.

DFS итеративно

Рекурсия в Python имеет лимит по умолчанию ~1000, а стек ОС в C++ — порядка 1 МБ. На больших графах ($n \ge 10^5$) рекурсивный DFS падает. Лекарство — итеративная реализация через явный стек:

BFS vs DFS — когда что

• Кратчайший путь в единичном графе — только BFS.
• Достижимость, компоненты связности — оба, выбирайте по удобству. Итеративные версии практически идентичны.
• Цикл в ориентированном графе, топологическая сортировка, двудольность, мосты, точки сочленения — DFS с раскраской WHITE/GRAY/BLACK и временем выхода. У BFS аналоги есть, но менее естественные.
• Поиск в дереве — рекурсивный DFS почти всегда удобнее. В условиях задачи дерево гарантировано, переполнения стека не будет, если переустановить лимит.

Главное практическое правило: если в задаче нужно знать расстояние — BFS. Если нужна структура обхода (порядок входа/выхода, рёбра дерева DFS) — DFS.

---

Компоненты связности — два подхода

Подход 1: через обход

Идём по всем вершинам. Если вершина ещё не посещена — запускаем из неё BFS или DFS, помечаем всех достижимых. Каждый запуск — новая компонента.

cnt ← 0
для v от 0 до n - 1:
    если не visited[v]:
        cnt ← cnt + 1
        DFS(v)        # или BFS(v)
вернуть cnt

Сложность: $O(n + m)$ суммарно (каждая вершина и ребро обходятся один раз).

Подход 2: через DSU (disjoint set union)

DSU держит структуру «множество элементов, разбитое на непересекающиеся классы», с операциями find(x) и union(x, y). Для каждого ребра $(v, u)$ вызываем union(v, u); в конце число различных корней = число компонент.

DSU dsu(n)
для каждого ребра (v, u):
    dsu.union(v, u)
cnt ← |{ dsu.find(v) : v ∈ [0, n) }|

Сложность: $O((n + m) \cdot \alpha(n))$ — практически линейная.

Когда что выбрать

• Граф уже задан списками смежности — обход проще и без зависимости от DSU.
• Граф задан списком рёбер и нужно отвечать на запросы «добавили ребро — сколько стало компонент» — DSU идеально, можно добавлять рёбра онлайн.
• Нужны не только компоненты, но и размер каждой — оба подходят, DSU поддерживает размер в массиве size[root].

---

Задача-иллюстрация 1: число островов (~CF 1200)

Условие

Дана сетка $n \times m$ из символов . (вода) и # (земля). Островом называется максимальная связная компонента из символов #, где две клетки считаются соседними, если они отличаются на одну координату ровно на 1 (4-связность). Найти число островов.

Ограничения. $1 \le n, m \le 1000$.

Пример.

5 5
#.#.#
.###.
#...#
.###.
#.#.#

Ответ: 5 — четыре угловых клетки и одна большая «крестообразная» компонента в центре.

Применение шаблона

Каждая клетка — вершина графа; рёбра — между парами соседних клеток одной природы (#–#). Идём по сетке слева направо, сверху вниз. Если встретили #, который ещё не посещён, — запускаем BFS из него, помечаем всю компоненту, увеличиваем счётчик.

Код решения

Что поменялось

Шаблон BFS применяется не к явно заданному графу, а к неявному графу сетки. Соседи вычисляются как клетки (x ± 1, y) и (x, y ± 1) с проверкой границ. Это типичный приём: половина «графовых» задач на олимпиадах — без явных списков смежности.

---

Задача-иллюстрация 2: проверка двудольности (~CF 1500)

Условие

Дан неориентированный граф из $n$ вершин и $m$ рёбер. Проверить, можно ли раскрасить все вершины в два цвета так, чтобы концы каждого ребра были разноцветными.

Ограничения. $1 \le n \le 10^5$, $0 \le m \le 2 \cdot 10^5$.

Сигнал и шаблон

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

Код решения

Что поменялось

Базовый BFS обогатился состоянием на вершине — цветом. Это типичный приём: вместо visited (бит) каждой вершине ставится в соответствие более содержательное значение (расстояние, цвет, предок в дереве BFS). Поиск кратчайшего пути из задачи 1 — это тот же шаблон, только в роли «цвета» — расстояние.

---

Задача-иллюстрация 3: число пар вершин в одной компоненте (~CF 1700)

Условие

Дан неориентированный граф $n$ вершин и $m$ рёбер. Найти число пар вершин $(u, v)$, $u < v$, между которыми существует путь.

Ограничения. $1 \le n \le 2 \cdot 10^5$, $0 \le m \le 2 \cdot 10^5$.

Шаблон

Связаны $u$ и $v$ тогда и только тогда, когда лежат в одной компоненте. В компоненте размера $k$ — $\binom{k}{2} = k(k-1)/2$ пар. Ответ — сумма по всем компонентам.

Применим DSU. Для каждого ребра — union. Затем считаем размер каждой компоненты по корням и суммируем.

Код решения

Что поменялось

Здесь BFS / DFS уступил место DSU, потому что нам не важна структура путей — важен только факт «в одной ли компоненте». DSU делает то же самое в среднем за $O(\alpha(n))$ на операцию, без хранения списков смежности (если они не нужны для другого). Ответ — long long, потому что $\binom{k}{2}$ при $k = 2 \cdot 10^5$ — это $\sim 2 \cdot 10^{10}$, не помещается в int.

---

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

1. Рекурсивный DFS на большом графе. В Python sys.setrecursionlimit(300000) иногда спасает, но при $n = 10^6$ упрётся в стек ОС. В C++ — поднять ulimit -s unlimited локально не вариант на удалённой системе тестирования. Лекарство — итеративная реализация через явный стек.
2. visited[start] = True забыт. При BFS легко забыть пометить источник перед началом цикла. Тогда мы вернёмся в источник через цикл и обработаем его повторно — либо WA, либо TLE на специально подобранных тестах.
3. В неориентированном графе ребро добавлено только в одну сторону. Распространённая баг при копипасте чужого кода для ориентированного графа.
4. dist[u] != INF вместо dist[u] == INF в проверке. Перепутанная логика — посещаем уже посещённые вершины. Бесконечная очередь, TLE.
5. Переполнение для подсчёта пар. $\binom{k}{2}$ для $k \ge 10^5$ — больше int. Использовать long long в C++, в Python переполнения нет.
6. DSU без сжатия путей или без объединения по рангу/размеру. Без оптимизаций — $O(n)$ на операцию, на $n = 10^5$ — на грани TL. Сжатие путей в find обязательно.
7. Сетка как граф: индексы вне границ. (x ± 1, y ± 1) без проверки 0 ≤ nx < n — segfault в C++, IndexError или странное поведение в Python.

---

Когда НЕ подходит

• Кратчайшие пути с разными весами рёбер. BFS гарантирует кратчайший путь только при единичных весах. Для произвольных неотрицательных весов — Дейкстра. Для произвольных весов (с отрицательными) — Беллман-Форд или Флойд.
• Все пары кратчайших расстояний. $n$ запусков BFS — $O(n(n + m))$, может не зайти. При $n \le 500$ — Флойд за $O(n^3)$.
• Очень плотный граф ($m \sim n^2$) при больших $n$. Список смежности съест память. Матрица — пройдёт, если $n \le 1000$. Иначе — задача требует структурного перехода (например, граф можно не строить явно).
• Динамические графы. Рёбра добавляются и удаляются — BFS / DFS приходится перезапускать. Для добавления — DSU. Для добавлений и удалений — отдельные техники (offline-DSU с откатами, link-cut trees), за рамками базы.

---

Связанные техники

• Дейкстра — обобщение BFS на положительные веса рёбер. Заменяет queue на priority_queue, время становится $O((n + m) \log n)$.
• 0-1-BFS — для рёбер веса 0 и 1, через двустороннюю очередь deque. Линейное время, без логарифма.
• DSU — альтернатива обходу для задач на связность без необходимости знать структуру путей.
• Топологическая сортировка — DFS с порядком выхода, на DAG. Базовый строительный блок для задач со «зависимостями».
• Поиск мостов и точек сочленения — DFS с временами входа и low-значениями. На олимпиадах CF 1700+.

---

Итого

• Техника: базовый шаблон обхода — BFS для расстояний, DFS для структуры; компоненты связности — через обход или DSU.
• Сложность шаблона: $O(n + m)$ для BFS / DFS, $O((n + m) \alpha(n))$ для DSU.
• Сигналы в условии: «связи / дороги / зависимости / сетка с препятствиями / достижимость / двудольность / компоненты».
• Типичные ловушки: глубокая рекурсия в Python и C++ (нужно итеративно), забытый visited[start], ребро только в одну сторону в неориентированном графе, переполнение в подсчёте пар.