Минимальные остовы

Авиакомпания содержит $m$ рейсов между $n$ городами, $i$-ый из них обходится в $w_i$ рублей, причём из любого города можно добраться до любого другого. В стране наступил кризис, и нужно отказаться от как можно большего числа из них таким образом, что содержание оставшиъся рейсов будет наиболее дешевым.

Иными словами, нужно найти дерево минимального веса, которое является подграфом данного неориентированного графа. Такие деревья называют остовами (каркас, скелет; ударение на первый слог, но так мало кто произносит). По-английски — minimum spanning tree (дословно, минимальное покрывающее дерево).

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

Вообще, следующие утверждения про деревья являются эквивалентными:

  • Граф — дерево.
  • В графе из $n$ вершин $n-1$ рёбер и нет циклов.
  • Из любой вершины можно дойти в любоую другую единственным образом.

Лемма о безопасном ребре

Назовем подграф $T$ графа $G$ безопасным, если они является подграфом какого-то минимального остова.

Назовем ребро безопасным, если при добавлении его в подграф $T$ получившийся граф $T'$ тоже является безопасным, то есть подграфом какого-то минимального остова.

Все алгоритмы для поиска минимального остова опираются на следующее утверждение:

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

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

safe

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

Алгоритм Прима

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

  • Изначально остов — одна произвольная вершина.
  • Пока минимальный остов не найден, выбирается ребро минимального веса, исходящее из вершины текущего остова в вершину, которую мы ещё не добавили. Добавляем это ребро в остов и начинаем заново, пока остов не будет найден.

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

Совсем наивная реализация за $O(nm)$ — каждый раз перебираем все рёбра:

In [ ]:
const int maxn = 1e5, inf = 1e9;
vector<int> from, to, weight;
bool used[maxn]

// считать все рёбра в массивы

used[0] = 1;
for (int i = 0; i < n-1; i++) {
    int opt_w = inf, opt_from, opt_to;
    for (int j = 0; j < m; j++)
        if (opt_w > weight[j] && used[from[j]] && !used[to[j]])
            opt_w = weight[j], opt_from = from[j], opt_to = to[j]
    used[opt_to] = 1;
    cout << opt_from << " " << opt_to << endl;
}

Реализация за $O(n^2)$:

In [ ]:
const int maxn = 1e5, inf = 1e9;
bool used[maxn];
vector< pair<int, int> > g[maxn];
int min_edge[maxn] = {inf}, best_edge[maxn];
min_edge[0] = 0;

// ...

for (int i = 0; i < n; i++) {
    int v = -1;
    for (int u = 0; u < n; j++)
        if (!used[u] && (v == -1 || min_edge[u] < min_edge[v]))
            v = u;
 
    used[v] = 1;
    if (v != 0)
        cout << v << " " << best_edge[v] << endl;
 
    for (auto e : g[v]) {
        int u = e.first, w = e.second;
        if (w < min_edge[u]) {
            min_edge[u] = w;
            best_edge[u] = v;
        }
    }
}

Можно не делать линейный поиск оптимальной вершины, а поддерживать его в приоритетной очереди, как в алгоритме Дейкстры. Получается реализация за $O(m \log n)$:

In [ ]:
set< pair<int, int> > q;
int d[maxn];

while (q.size()) {
    v = q.begin()->second;
    q.erase(q.begin());
 
    for (auto e : g[v]) {
        int u = e.first, w = e.second;
        if (w < d[u]) {
            q.erase({d[u], u});
            d[u] = w;
            q.insert({d[u], u});
        }
    }
}

Про алгоритм за $O(n^2)$ забывать не стоит — он работает лучше в случае плотных графов.

Алгоритм Крускала

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

Звучит очень просто — отсортировать все рёбра, пройтись по ним циклом и делать проверку, что вершины в разных компонентах. Однако для этой проверки нам нужна будет целая отдельная структура.

Система непересекающихся множеств

Эта структура данных предоставляет следующие возможности. Изначально имеется несколько элементов, каждый из которых находится в отдельном (своём собственном) множестве. Структура поддерживает две операции:

  • объединить два каких-либо множества
  • запросить, в каком множестве сейчас находится указанный элемент

Обе операции будут выполняться в среднем почти за $O(1)$ (но не совсем — этот сложный вопрос будет разъяснен позже).

Множества элементов мы будем хранить в виде деревьев: одно дерево соответствует одному множеству. Корень дерева — это представитель (лидер) множества. Заведём массив _p, в котором для каждого элемента мы храним номер его предка в дерева. Для корней деревьев будем считать, что их предок — они сами.

Наивная реализация, которую мы потом ускорим:

In [ ]:
int _p[maxn];

int p (int v) {
    if (_p[v] == v)
        return v;
    else
        return p(_p[v]);
}

void unite (int a, int b) {
    a = p(a), b = p(b);
    _p[a] = b;
}

for (int i = 0; i < n; i++)
    _p[i] = i;

Эвристика сжатия пути. Оптимизируем работу функции p. Давайте перед тем, как вернуть ответ, запишем его в _p от текущей вершины, то есть переподвесим его за самую высокую.

Насколько лучше это сделает асимптотику? Выясняется, что $O(n \log n)$.

Тут должен быть мем из опросов.

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

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

Автор предпочитает именно её, потому что часто эти размеры компонент требуются сами по себе.

Оказывается, что сжатия + ранговая или сжатия + весовая работает быстро.

Асимптотика объединения обеих эвристик (сжатия путей и одной из ранговых) — O(a(n)), где a(n) — обратная функция Аккермана (очень медленно растущая функция, для всех адекватных чисел не превосходящая 4). Тратить время на изучения доказательства или даже чтения статьи на Википедии про функцию Аккермана автор не рекомендует.

In [ ]:
int _p[maxn], s[maxn];

int p (int v) { return (_p[v] == v) ? v : _p[v] = p(_p[v]); }

void unite (int a, int b) {
    a = p(a), b = p(b);
    if (s[a] > s[b]) swap(a, b);
    s[b] += s[a];
    _p[a] = b;
}

for (int i = 0; i < n; i++)
    _p[i] = i;

Полезные свойства и классические задачи

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

Персистентная СНМ*

Как вы уже заметили, автор очень любит персистентные структуры данных.

СНМ — тоже структура, и её тоже можно сделать персистентной. В СНМ мы изменяем массивы, а массивы можно сделать персистентными через персистентное ДО (только так, проще не получается — многие пытались).

Здесь есть нюанс — амортизированные структуры не очень хорошо дружат с персистентностью. Поэтому нам придется отказаться от эвристики сжатия путей, и поэтому асимптотика составит $O(n \log^2 n)$ времени и памяти — один логарифм от СНМа, другой от персистентного ДО.

Динамическая связность*

Dynamic Connectivity Problem:

Даны $n$ запросов добавления ребра (+), удаления ребра (- и какого-то запроса про граф (?), например, о связности двух вершин.

О решении этой задачи в online и в offline можете почитать в этом посте.