Поиск в глубину и мосты

1. Стек вызовов и рекурсия

Стек работает по принципу LIFO (last in, first out): положить сверху, достать тоже сверху. Последний пришел — первым ушел. (FIFO — это очередь.)

Пусть функция A вызывает B, B вызывает C, а C вызывает print. Что происходит в стеке вызовов:

A вызвала B и замораживается: ждет, когда к ней вернутся;
B вызвала C и тоже замораживается;
C вызвала print (это тоже функция, просто «из коробки») и замораживается;
на вершине стека всегда лежит функция, которая выполняется сейчас. Когда print отработал, он вылетает из стека, C продолжает работу, завершается, и так по цепочке вниз.

Рекурсия — функция вызывает саму себя. Механика та же самая, просто в стеке лежат одноименные функции с разными параметрами. Пример: факториал.

python

def f(n):
    if n == 1:
        return 1
    return n * f(n - 1)

f(5) вызывает f(4) и замирает, f(4) вызывает f(3) и так далее до f(1), которая возвращает 1. Дальше стек «раскручивается» вниз: 2·1 = 2, 3·2 = 6, … и в итоге 120.

Stack overflow — переполнение стека вызовов: слишком много вложенных вызовов одновременно. Одна из самых частых ошибок. (Так же называется сайт вопросов и ответов по программированию, но теперь эту базу знаний скормили нейросетям, и они отвечают вместо него)

2. Терминология: граф, сеть, ребро и дуга

Граф — множество вершин $V$ и множество ребер $E$ . Он может быть невзвешенным и неориентированным.
Сеть — граф, у которого заданы функция на ребрах (веса, пропускные способности) и, как правило, ориентация.
«Задана функция на ребрах» значит, что каждому ребру сопоставили число (целое или вещественное), то есть одному дискретному множеству сопоставили другое. Курс — комбинаторные алгоритмы оптимизации: мы оптимизируем и работаем с дискретными, комбинаторными объектами.
Ребро — «палочка» без направления, дуга (arc) — палочка со стрелкой. Говоря «дуга», всегда подразумевают ориентированный граф. В русскоязычной литературе часто говорят просто «ребра», а бывают они ориентированные или нет — оговаривают отдельно. В иностранной литературе вы встретите именно edge (ребро) и arc (дуга).

Вершины графа обычно индексируют числами от $0$ до $n - 1$ . Граф может быть несвязным — состоять из нескольких компонент связности.

3. DFS: поиск в глубину

DFS — обход графа, который идет вглубь, пока есть куда идти. Рассмотрим граф из двух компонент, вершины пронумерованы, и запустим DFS из вершины $0$ , всегда выбирая из соседей вершину с меньшим номером.

Стек активных вершин

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

Алгоритм:

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

Иногда это объясняют на примере очень обидчивой змеи: уперлась в тупик, обиделась и больше туда не возвращается.

Стек в любой момент хранит простой путь от стартовой вершины до текущей (например, $0 \to 1 \to 5 \to 2$ ). Поэтому его и называют стеком активных вершин. «Простой» значит, что никакая вершина (и ребро) не повторяется.

Свойства

Каждая вершина побывает в стеке ровно один раз, и каждое ребро мы «пощупаем» тоже ограниченное число раз (при условии, что не просматриваем список заново после возврата). Итого асимптотика $O (V + E)$ .
Ребра, по которым мы реально прошли, образуют дерево обхода DFS. В нем на одно ребро меньше, чем посещенных вершин (посетили 5 вершин — в дереве 4 ребра).
DFS не гарантирует, что будут обойдены все вершины: в неориентированном графе он обойдет только ту компоненту связности, в которой лежит стартовая вершина. Чтобы обойти весь граф, запускаем DFS от каждой еще не посещенной вершины.

4. Рекурсивная реализация DFS

python

used = [False] * n          # где были
adj = [...]                 # список смежности

def dfs(v):
    used[v] = True          # зашли — сразу помечаем
    for to in adj[v]:
        if not used[to]:
            dfs(to)

Что в стеке вызовов при запуске dfs(0): вызван dfs(0), он запускает цикл for по соседям, находит непосещенную вершину $1$ и вызывает dfs(1). Цикл for в dfs(0) при этом замораживается на месте, где остановился, и ждет возврата. Дальше dfs(1) запускает свой цикл и так далее.

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

5. Мосты

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

5.1. Классификация ребер при обходе

Запустим DFS и посмотрим на все ребра, которые он просматривает.

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

Если перерисовать дерево обхода по уровням, у каждой вершины появляется глубина (нумеруем с единицы: корень — 1, его ребенок — 2 и т. д.), а обратные ребра выглядят как дуги, идущие вверх.

Ключевое наблюдение. Обратное ребро замыкает цикл, а ребро на цикле не может быть мостом. Значит, мосты — это ровно те ребра дерева обхода, над которыми нет ни одного обратного ребра, «перепрыгивающего» их.

5.2. Идея алгоритма

Для каждой вершины $v$ храним две величины:

$d [v]$ — глубина вершины в дереве обхода (ставим при заходе);
$h [v]$ — минимальная глубина, которой можно достичь, стартуя из $v$ : спускаясь по дереву и сделав не более одного обратного ребра.

Как они считаются:

При заходе в $v$ : $d [v] = h [v] = d [parent] + 1$ .
Если из $v$ смотрим на уже посещенную вершину $t o$ (обратное ребро): «вытаскиваем» ее глубину, $h [v] = min (h [v], d [t o])$ . Мы туда не идем, просто запоминаем: из $v$ можно добраться до глубины $d [t o]$ .
Если $t o$ не посещена, идем в нее (прямое ребро). При откате из $t o$ в $v$ тащим наверх накопленный минимум: $h [v] = min (h [v], h [t o])$ .

Минимум «протаскивается» вдоль пути назад по дереву обхода

Признак моста. Вернулись из $t o$ в $v$ (ребро $v \to t o$ — прямое). Если

h [t o] > d [v],

то это мост. Поясним: мы сходили в поддерево $t o$ , погуляли там и не нашли ни одного пути в $v$ или выше (самое высокое, куда добрались, — глубина $h [t o]$ , и она больше, чем глубина $v$ ). Раз пути вверх нет, поддерево $t o$ связано с остальным графом только этим ребром. Если же $h [t o] \leq d [v]$ , то из поддерева есть путь к предку $v$ (или в саму $v$ ), мы в цикле, значит, не мост.

Мосты можно определять во время единственного обхода: второй проход не нужен.

5.3. Мелочь: не считать ребро к родителю обратным

Находясь в вершине $1$ (пришли из $0$ ), мы увидим в списке смежности вершину $0$ , где уже были. Но это то же самое ребро дерева, по которому мы пришли, а не обратное. Поэтому передаем в dfs еще и родителя и пропускаем его:

cpp

if (to == parent) continue;

Обратное ребро идет в вершину строго на уровень выше родителя. «Пошел по дереву, вернулся по тому же ребру и объявил его обратным» — бред.

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

6. Реализация на C++

Граф вводим как «число вершин, число ребер, затем ребра». Список смежности — вектор векторов. push_back здесь подходит: emplace_back быстрее не будет.

cpp

#include<functional>
#include<vector>
#include<iostream>

int main(){
    size_t n = 0, m = 0;
    std::cin >> n >> m;
    std::vector<std::vector<size_t>> adj(n);
    for (size_t i = 0; i < m; ++i>){
        size_t v = 0, u = 0;
        std::cin >> v >> u;
        adj[v].push_back(u);
        adj[u].push_back(v);
    }
    std::vector<int> h_cur(n);
    std::vector<int> h_min(n);
    std::vector<int> used(n);

    std::function<void(int, int)> dfs = [&](const int v, const int p = -1)->void {
        used[v] = true;
        h_cur[v] = h_min[v] = h_cur[p] + 1;
        for (const auto &to: adj[v]){
            if (to == p) continue;                                      // не считаем ребро в родителя обратным
            if (!used[to]){
                dfs(to, v);
                h_min[v] = std::min(h_min[v], h_min[to]);               // откат: тащим минимум наверх
            } else {
                h_min[v] = std::min(h_min[v], h_cur[to]);               // обратное ребро: вытаскиваем глубину
            }
        }
        ; 
    };
    dfs(0, 0);
}

Замечания:

vector<int>, а не vector<bool>, для used. vector<bool> сжимает каждый элемент до одного бита и при каждом обращении вычисляет нужный байт и бит битовыми операциями. Это заметно медленнее.
Бывали задачи на DFS по ~ $10^{6}$ вершин, где с vector<bool> получали time limit на двух секундах, а после замены на vector<int> укладывались в 400–500 мс. Правило: не хватает памяти — vector<bool>, не хватает времени — vector<int>. По умолчанию берем int.
Проверка признака моста стоит после возврата из dfs(to, v) и после обновления h[v]. Обновлять h[v] по h[to] нужно именно после возврата: к этому моменту поддерево to полностью обойдено.

Проверка на примере

Граф из 10 вершин и 11 ребер (цепочки и циклы, нарисованные в лекции). Напечатанные $d$ и $h$ для нескольких вершин:

вершина $0$ : $d = 1$ , вершина $1$ : $d = 2$ , $h = 2$ (вверх выйти нельзя) → ребро $0 – 1$ мост;
вершина $4$ (глубина 5): пошла по прямому ребру дальше и достигла только глубины 5 → ребро мост;
в циклической части $h$ у нескольких вершин равны 2 или 3 (протащено по обратному ребру), эти ребра мостами не являются.

Программа нашла пять мостов: $0 – 1$ , $1 – 2$ , $0 – 5$ , $4 – 9$ , $7 – 8$ . Затем добавили ребро $4 – 7$ (стало 12 ребер): оно замкнуло большой цикл, и мостами остались только $4 – 9$ и $7 – 8$ — остальные оказались на цикле.

Почему алгоритм не ломается при нескольких обратных ребрах

Любое число обратных ребер из поддерева лишь уменьшает $h$ (мы берем минимум), то есть делает «поднятие» вверх еще более очевидным. Каждое обратное ребро в итоге «закрывает» все прямые ребра на пути между собой и своим верхним концом.

Поиск в глубину и мосты ​

1. Стек вызовов и рекурсия ​

2. Терминология: граф, сеть, ребро и дуга ​

3. DFS: поиск в глубину ​

Стек активных вершин ​

Свойства ​

4. Рекурсивная реализация DFS ​

5. Мосты ​

5.1. Классификация ребер при обходе ​

5.2. Идея алгоритма ​

5.3. Мелочь: не считать ребро к родителю обратным ​

6. Реализация на C++ ​

Проверка на примере ​

Почему алгоритм не ломается при нескольких обратных ребрах ​