Обход графа: поиск в ширину и в глубину

Почти любая задача про графы начинается с обхода. Ниже — полная теория из курса «Кружок 102» про два базовых обхода: в ширину (BFS) и в глубину (DFS).

Поиск в ширину (BFS)

Зачем нужен обход в ширину

Есть граф — дороги между городами, клетки лабиринта, состояния головоломки, друзья в соцсети. Часто нужен не любой путь из точки A в точку B, а самый короткий: минимальное число дорог, минимальное число ходов, минимальное число рукопожатий. Если все рёбра «одинаковой длины» (невзвешенный граф — каждый шаг стоит единицу), то для этого существует красивый и очень дешёвый по времени алгоритм — обход в ширину, breadth-first search, BFS.

Интуиция такая: представь, что в вершине s ты поджигаешь бумагу. Огонь распространяется вдоль рёбер с одинаковой скоростью — за одну единицу времени переходит на всех соседей уже горящих вершин. Тогда вершина загорается ровно в момент времени, равный длине кратчайшего пути до неё. BFS — это симуляция такого пожара: сначала обрабатываем сам источник, потом всех, кто на расстоянии 1, потом всех, кто на расстоянии 2, и так далее — слой за слоем, ширина за шириной. Отсюда и название.

Это принципиально отличается от DFS (обхода в глубину), который ныряет в одну ветку до упора и не даёт никакой гарантии кратчайшести. BFS специально устроен так, чтобы обрабатывать вершины в порядке неубывания расстояния от старта.

Почему это вообще работает

Утверждение, на котором всё держится: если обходить вершины волнами (слоями) L₀ = s, L₁, L₂, …, где L_k — множество всех вершин на расстоянии ровно k от s, то каждая вершина попадёт ровно в свой слой, и раньше она попасть не может.

Доказательство по индукции. База: L₀=s, расстояние от s до себя — 0, всё верно. Переход: пусть для всех слоёв до k включительно утверждение верно (в L_i лежат ровно вершины на расстоянии i). Рассмотрим вершину u, до которой кратчайшее расстояние равно k+1. Тогда на кратчайшем пути в u предпоследняя вершина v имеет расстояние ровно k (иначе путь не был бы кратчайшим или существовал бы более короткий путь через ещё более раннего предка — но тогда и до u было бы расстояние меньше k+1, противоречие). Значит, v ∈ L_k, и когда алгоритм обрабатывает слой L_k, он смотрит на всех соседей v, включая u, и, если u ещё не посещена, кладёт её в L_k+1 с расстоянием k+1. С другой стороны, u не может оказаться ни в каком более раннем слое: если бы она была помечена на шаге j < k+1, то её расстояние равнялось бы j (по предположению индукции для всех предыдущих слоёв), что противоречит тому, что настоящее кратчайшее расстояние — k+1.

Отсюда сразу следует ключевой факт: первый раз, когда мы достигаем вершину в BFS, — это и есть кратчайшее расстояние до неё. Как только вершина помечена посещённой, её расстояние (и путь через предка) больше никогда не меняется — пересматривать нечего.

Обрати внимание: доказательство существенно использует, что все рёбра «весят» одинаково — единицу. Если веса рёбер разные, слоистая структура ломается: может случиться, что путь короче по числу рёбер, но длиннее по сумме весов, и BFS даёт неверный ответ. Для взвешенных графов нужен алгоритм Дейкстры (или Форда-Беллмана для отрицательных весов) — оба разберём на уровне 6.

Реализация

Алгоритм использует очередь FIFO — первым пришёл, первым вышел. Именно очередь (а не стек, как в DFS) гарантирует, что мы разбираем вершины строго по слоям: пока не обработаны все вершины слоя k, ни одна вершина слоя k+1 не начнёт обрабатываться раньше времени.

pair<vector<int>, vector<int>> bfs(vector<vector<int>>& g, int start) {
    int n = g.size();
    vector<int> dist(n, -1);     // -1 значит «ещё не найдено»
    vector<int> parent(n, -1);   // для восстановления пути
    dist[start] = 0;
    queue<int> q;
    q.push(start);
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (int u : g[v]) {
            if (dist[u] == -1) {
                dist[u] = dist[v] + 1;
                parent[u] = v;
                q.push(u);
            }
        }
    }
    return {dist, parent};
}

Восстановить путь до вершины t можно, идя по массиву parent от t к start и потом развернув список.

Если путь восстанавливать не нужно, parent можно выкинуть — остаётся минимальный каркас BFS, который и стоит держать в голове (посещённость здесь хранится прямо в условии dist[u] == -1, отдельный vector<bool> не нужен):

vector<int> bfs(vector<vector<int>>& g, int start) {
    int n = g.size();
    vector<int> dist(n, -1);
    dist[start] = 0;
    queue<int> q;
    q.push(start);
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (int u : g[v]) {
            if (dist[u] == -1) {
                dist[u] = dist[v] + 1;
                q.push(u);
            }
        }
    }
    return dist;
}

Важная деталь: помечать вершину посещённой (обновлять dist) нужно в момент добавления в очередь, а не в момент извлечения из неё. Если пометить только при извлечении, одна и та же вершина может попасть в очередь несколько раз (её добавят все соседи, которые до неё дошли раньше, чем она сама была обработана), и это не сломает корректность результата, но может резко увеличить число операций — вплоть до потери линейной сложности на плотных графах.

Сложность

Каждая вершина кладётся в очередь и вынимается из неё не более одного раза (при условии, что помечаем сразу при добавлении) — это O(V) операций с очередью. Для каждой вынутой вершины мы проходим по её списку смежности, а суммарная длина всех списков смежности по графу равна O(E) (для неориентированного графа — 2E, но это те же асимптотики). Итого время работы — O(V + E), линейное по размеру графа. Память — тоже O(V + E): сам граф плюс массивы dist, parent и очередь.

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

Многоисточниковый BFS

Часто нужно найти кратчайшее расстояние не от одной точки, а от ближайшей из нескольких сразу — например, расстояние до ближайшего выхода, до ближайшего источника воды на карте, до ближайшей заражённой клетки. Решение элегантное: не нужно запускать BFS отдельно для каждого источника и брать минимум — достаточно положить все источники в очередь сразу, присвоив им всем расстояние 0, и запустить один обычный BFS.

Корректность следует из того же рассуждения про слои: если считать, что стартовый слой L₀ состоит из всех источников одновременно, то L_k — это в точности множество вершин, чьё расстояние до ближайшего источника равно k. Доказательство один в один повторяет доказательство для одного источника, просто база индукции чуть шире.

BFS на неявных графах

Многие задачи не дают граф явным списком вершин и рёбер — граф нужно строить «на лету». Классический пример: лабиринт на сетке n × m, где вершины — клетки, а рёбра — переходы в 4 (или 8) соседних клетки, не являющихся стенами. Здесь просто на каждом шаге вместо перебора списка смежности перебирают соседние клетки по формуле ((x+1,y), (x-1,y), (x,y+1), (x,y-1)), проверяя, что они в пределах поля и проходимы. Стандартный приём — массивы смещений dx/dy, чтобы не писать четыре одинаковых блока:

int n, m;
cin >> n >> m;
vector<string> field(n);
for (auto& row : field) cin >> row;          // '.' — свободно, '#' — стена
int sx = 0, sy = 0;                          // старт помечен символом 'S'
for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
        if (field[i][j] == 'S') { sx = i; sy = j; }

vector<vector<int>> dist(n, vector<int>(m, -1));
int dx[] = {1, -1, 0, 0};                    // четыре направления
int dy[] = {0, 0, 1, -1};
queue<pair<int,int>> q;
dist[sx][sy] = 0;
q.push({sx, sy});
while (!q.empty()) {
    auto [x, y] = q.front(); q.pop();
    for (int d = 0; d < 4; d++) {
        int nx = x + dx[d], ny = y + dy[d];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;  // вышли за поле
        if (field[nx][ny] == '#' || dist[nx][ny] != -1) continue;
        dist[nx][ny] = dist[x][y] + 1;
        q.push({nx, ny});
    }
}
// dist[i][j] — кратчайшее число шагов от S до клетки (i, j), -1 если недостижима

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

Дополнительные применения

Помимо кратчайших путей в невзвешенном графе, BFS (как и DFS) годится для поиска компонент связности — достаточно запускать его из каждой ещё не посещённой вершины и считать, сколько раз пришлось это сделать. Он же удобен для проверки двудольности графа: при обходе красим вершины в два цвета поочерёдно по слоям (чётный слой — цвет A, нечётный — цвет B) и если находим ребро между двумя вершинами одного цвета — граф не двудольный, потому что найден цикл нечётной длины.

BFS также даёт естественный способ найти кратчайший цикл, проходящий через фиксированную вершину или ребро: удаляем ребро (u, v), запускаем BFS от u и смотрим на dist[v] — кратчайший цикл через это ребро равен dist[v] + 1. А чтобы восстановить не только длину, но и сам путь до нужной вершины, достаточно хранить массив предков parent[] и один раз пройти по нему от цели к источнику — это работает, потому что дерево BFS (совокупность рёбер parent[u] -> u) как раз и является деревом кратчайших путей от источника ко всем остальным вершинам.

Поиск в глубину (DFS)

Поиск в глубину (depth-first search) — это способ обойти граф, при котором мы идём вперёд настолько далеко, насколько можем, а когда упираемся в тупик — откатываемся назад и пробуем другой путь. Это буквально то, что делает человек, блуждающий по лабиринту с мотком нити: идём по коридору, если он тупиковый — возвращаемся к последней развилке и пробуем следующий поворот.

Это, скорее всего, ваша первая встреча с графами, поэтому начнём с самого начала.

Что такое граф

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

В программе граф удобнее всего хранить списками смежности: для каждой вершины держим вектор номеров её соседей. Считывается это так:

int n, m;                      // число вершин и рёбер
cin >> n >> m;
vector<vector<int>> g(n);      // g[v] — список соседей вершины v
for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    u--; v--;                  // в условиях вершины обычно с 1, в коде — с 0
    g[u].push_back(v);
    g[v].push_back(u);         // для ориентированного графа эту строку убрать
}

Сам обход

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

vector<vector<int>> g; // список смежности
vector<char> used;

void dfs(int v) {
    used[v] = true;
    for (int to : g[v]) {
        if (!used[to]) {
            dfs(to);
        }
    }
}

Ключевая деталь, из-за которой всё работает корректно, — массив used. Без него алгоритм зациклился бы на первом же цикле в графе, бесконечно бегая по кругу. С ним каждая вершина обрабатывается ровно один раз, а каждое ребро просматривается ровно дважды (по одному разу с каждого конца, если граф неориентированный) или один раз (если ориентированный).

Отсюда сразу следует оценка сложности: O(V + E) — линейно от суммарного размера графа (число вершин плюс число рёбер). Это оптимально: быстрее, чем прочитать входные данные, обойти граф в принципе нельзя.

Компоненты связности

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

Чтобы обойти весь граф, перебираем все вершины и запускаем DFS из каждой ещё не посещённой. Каждый такой запуск красит ровно одну компоненту связности — кусок графа, внутри которого всё связано, а с остальными кусками связи нет. Отсюда первое практическое применение: чтобы посчитать число компонент, достаточно посчитать, сколько раз пришлось стартовать DFS заново:

int components = 0;
for (int v = 0; v < n; v++) {
    if (!used[v]) {
        components++;
        dfs(v);
    }
}

DFS по клеткам сетки (flood fill)

Очень частая задача выглядит как поле из клеток: карта, лабиринт, картинка. Проходимые клетки — точки, стены — решётки; нужно, например, посчитать число «островов» или залить одну связную область.

Тут граф никто явно не задаёт — его роль играет сама сетка. Вершина — это клетка (r, c), а соседи — четыре клетки сверху, снизу, слева и справа (иногда добавляют ещё четыре диагональных). Такая заливка связной области называется flood fill («заливка», как ведёрко в графическом редакторе). Отдельный список смежности строить не нужно: соседей вычисляем на лету по смещениям.

int R, C;
vector<string> grid;         // '.' — проходимо, '#' — стена
vector<vector<char>> used;

int dr[] = {-1, 1, 0, 0};    // смещения по строке
int dc[] = {0, 0, -1, 1};    // и по столбцу для 4 направлений

void dfs(int r, int c) {
    used[r][c] = true;
    for (int d = 0; d < 4; d++) {
        int nr = r + dr[d], nc = c + dc[d];
        if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue; // вышли за поле
        if (grid[nr][nc] == '#' || used[nr][nc]) continue;     // стена или уже были
        dfs(nr, nc);
    }
}

Обратите внимание на две проверки: сначала не выходим ли мы за границы поля, потом — не стена ли это и не были ли мы тут раньше. Всё остальное — тот же самый DFS, просто «соседи» вычисляются арифметикой, а не берутся из g[v]. Число островов считается ровно как число компонент связности: перебираем клетки и стартуем заливку из каждой ещё не посещённой проходимой клетки.

Проверка на цикл

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

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

bool hasCycle = false;

void dfs(int v, int parent) {
    used[v] = true;
    for (int to : g[v]) {
        if (to == parent) continue;   // назад к родителю — не цикл
        if (used[to]) {
            hasCycle = true;          // обратное ребро — нашли цикл
        } else {
            dfs(to, v);
        }
    }
}

Пропускаем ровно ребро к родителю. Если во входных данных могут быть кратные рёбра (два ребра между одной парой вершин), надёжнее пропускать по номеру ребра, а не по номеру вершины, но для простых графов версии выше достаточно. На этой проверке, кстати, целиком строятся задачи вида «является ли граф деревом»: дерево — это связный граф без циклов, то есть ровно одна компонента связности и ни одного обратного ребра.

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

Пусть граф ориентированный и в нём нет циклов — такой граф называют DAG (directed acyclic graph, ориентированный ациклический граф). Классический пример — зависимости: чтобы выполнить задачу, надо сначала сделать все, от которых она зависит. Хочется выстроить вершины в линию так, чтобы все рёбра шли слева направо. Это и есть топологическая сортировка.

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

vector<int> order;

void dfs(int v) {
    used[v] = true;
    for (int to : g[v]) if (!used[to]) dfs(to);
    order.push_back(v);   // момент выхода из вершины
}
// в конце: reverse(order) — и это топологический порядок

Почему работает: для любого ребра (u, v) вершина v полностью обрабатывается и выходит раньше, чем выходит u (либо она вложена в обход u, либо была обработана ещё раньше). Значит в списке order вершина v окажется левее u, а после разворота — правее. То есть после reverse каждое ребро направлено слева направо, что нам и нужно. Если же в графе есть цикл, топологического порядка не существует в принципе — как раз наличие обратного ребра это и ловит.

Итеративная версия и переполнение стека

Рекурсивный DFS элегантен, но у него есть практическая проблема: на графе с длинной цепочкой из 10⁵–10⁶ вершин глубина рекурсии окажется такого же порядка, а стандартный стек вызовов ограничен (обычно несколько МБ, то есть десятки тысяч кадров). Результат — падение по stack overflow, причём именно на больших или цепочечных тестах, что коварно: на маленьких примерах всё работало.

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

void dfs_iter(int start) {
    vector<int> st = {start};
    used[start] = true;
    while (!st.empty()) {
        int v = st.back();
        st.pop_back();
        for (int to : g[v]) {
            if (!used[to]) {
                used[to] = true;
                st.push_back(to);
            }
        }
    }
}

Обратите внимание: здесь порядок обхода не совпадает точно с рекурсивным DFS, и мы не отслеживаем момент «выхода» из вершины (значит, для топосорта такой вариант в лоб не подойдёт). Но для задач, где важен сам факт достижимости, компоненты связности или заливка, этого достаточно, и это самый короткий надёжный способ не переполнить стек вызовов.

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

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

Иногда граф хранят матрицей смежности — таблицей n × n, где на пересечении строки u и столбца v стоит признак «есть ли ребро между u и v». Ответить на вопрос «есть ли ребро?» по ней можно мгновенно, но у DFS с ней беда: чтобы найти соседей вершины, приходится перебирать всю строку из n клеток, и сложность обхода становится O(V²) вместо O(V+E). На разреженных графах (где рёбер сильно меньше, чем V²) это заметно медленнее.

Поэтому для DFS почти всегда используют списки смежности (vector<vector<int>>), а матрицу держат только когда граф действительно плотный или когда нужен именно быстрый ответ «есть ли ребро между u и v».

Итог: что даёт DFS

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

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