Обход в ширину

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

Пусть нам дан граф и надо найти кратчайший путь от $s$ до $t$ или сказать, что такого пути нет.

Запустим “волну” из $s$, которая будет каждую итерацию распространяться на все вершины, соседние с уже задетыми “ волной”, но ещё не посещённые. Нетрудно заметить, что расстояние между $s$ и $t$ в такой модели - номер итерации, на которой была использована вершина $t$. Если $t$ не была использована, то расстояние - $+\infty$.

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

Реализация

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

Кроме того, будем поддерживать расстояние до каждой вершины: $d[s] = 0$, а когда мы кладём новую вершину $u$ через её соседа $v$, объявим $d[u] = d[v] + 1$. Изначально массив $d$ будет заполнен $+\infty$. Он же будет служить массивом $used$: у посещённых вершин значение $d$ будет меньше бесконечности, а у непосещённых - $+\infty$.

int n;
vector<int> d(n, INF), p(n, -1);
vector<vector<int>> g(n);

vector<int> bfs(int s, int t) {
    d[s] = 0;
    queue<int> q{s};
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        
        for (int u : g[v]) {
            if (d[v] + 1 < d[u]) {
                d[u] = d[v] + 1;
                p[u] = v;
                q.push(u);
            }
        }
    }
    
    vector<int> res{t};
    while (p[res.back()] != -1) {
        res.push_back(p[res.back()]);
    }
    reverse(res.begin(), res.end());
    return res;
}

Асимптотика

Нетрудно заметить, что каждую вершину посетили один раз и при этом перебрали все рёбра, исходящие из неё.

Тогда асимптотика - $O(n + m)$.

Вариации

У алгоритма существует много модификаций. Тут рассмотрим несколько из них:

0-1 BFS

В этой модификации допустимы два веса рёбер - 0 и 1.

Для решения задачи создадим две очереди вместо одной - в первую будем класть вершины, по которым мы дошли через 0-ребро, а во вторую - те, до которых мы дошли через 1-ребро.

Теперь каждый раз, прежде чем рассмотреть новую вершину из 1-очереди, будем рассматривать все вершины из 0-очереди, пока она не станет пустой.

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

Таким образом мы берём обычный BFS, но перед рассмотрением каждой вершины рассматриваем всё, достижимое по нулям.

Пути в таблице

Часто встречаются задачи, когда граф представлен таблицей, где какие-то клетки можно посещать, а другие - нельзя (пусть это хранится в массиве $a$ - от available).

Такие таблицы можно приводить к графам и решать задачу о поиске пути обычнымм методом, но как правило удобнее работать с таким графом как с таблицей.

Поскольку мы не храним рёбра явно, нам нужно уметь получать их по $(x,y)$ текущей клетки.

Для этого удобно использовать массив сдвигов $dx$, $dy$: мы запоминаем, каким образом могут измениться координаты клетки за один ход, записываем в заранее созданный массив и вместо обычного цикла по смежным вершинам перебираем сдвиги.

Затем считаем новые координаты и проверим, валидна ли полученная клетка, то есть не вышли ли мы за границы массива, и доступна ли она. Данные проверки полезно выносить в отдельную функцию $check(x, y)$.

Например, так это будет выглядеть, когда из клетки можно ходить в соседей по горизонтали или вертикали:

bool check(x, y) {
    return 0 <= x && x < n && 0 <= y && y < m && a[x][y] == 1;
}

vector<pair<int, int>> d{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

while (!q.empty()) {
    ...
    for (auto [dx, dy] : d) {
        int x1 = x + dx, y1 = y + dy;
        if (check(x1, y1)) {
            ...
        }
    }
}