Skip to content

Latest commit

 

History

History
265 lines (175 loc) · 19.5 KB

mst.md

File metadata and controls

265 lines (175 loc) · 19.5 KB
Raw

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

Рассмотрим следующую задачу:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

const int maxn = 1e5, inf = 1e9;
vector 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)$:

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)$:

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)$ забывать не стоит — он работает лучше в случае плотных графов.

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

Система непересекающихся множеств (англ. disjoint set union) — структура данных, которая используется для хранения информации о связности компонент. Она нам потребуется для описания следующего подхода — алгоритма Крускала.

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

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

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

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

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

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 от текущей вершины, то есть переподвесим его за самую высокую.

Паблик «Странные опросы для спортивных программистов»

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

Ранговая эвристика. Будем хранить для каждой вершины её ранг — высоту её поддереа. При объединении деревьев будем делать корнем нового дерева ту вершину, у которой ранг больше, и пересчитывать ранги (ранг у лидера должен увеличиться на единицу, если он совпадал с рангом другой вершины). Эта эвристика оптимизирует высоту дерева напрямую.

Весовая эвристика. Будем вместо ранга хранить размеры поддеревьев для каждой вершины, а при объединении — подвешивать за более «тяжелую».

Финальная реализация, использующая весовую эвристику и эвристику сжатия путей:

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;
}

// где-то в main:

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

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

Асимптотика

Эвристика сжатия путей улучшает асимптотику до $O(\log n)$ в среднем. Здесь используется именно амортизированная оценка — понятно, что в худшем случае нужно будет сжимать весь бамбук за $O(n)$.

Индукцией несложно показать, что весовая и ранговая эвристики ограничивают высоту дерева до $O(\log n)$, а соответственно и асимптотику тоже.

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

Тратить время на изучения доказательства или даже чтения статьи на Википедии про функцию Аккермана автор не рекомендует.

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

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

Звучит очень просто — отсортировать все рёбра, пройтись по ним циклом и делать проверку, что вершины в разных компонентах. Наивная проверка будет работать за $O(m \log m + n^2)$, но асимптотику можно улучшить до $O(m \log m)$ (до стоимости сортировки), если для проверок использовать систему непересекающихся множеств.

// (w, (a, b))
vector< pair< int, pair<int, int> > > edges;

sort(edges.begin(), edges.end());

for (auto e : edges) {
    int a = e.first.first, b = e.first.second;
    // компоненты разные, если лидеры разные
    if (p(a) != p(b)) {
        // добавим ребро (a, b)
        unite(a, b);
    }
}

Алгоритм Борувки

Лемма. Для любой вершины минимальное инцидентное ей реборо является безопасным.

Доказательство. Пусть есть минимальный остов, в котором для какой-то вершины $v$ нет её минимального инцидентного ребра. Тогда, если добавить это ребро, образуется цикл, из которого можно удалить другое ребро, тоже инцидентное $v$, но имеющее не меньший вес.

Алгоритм Борувки опирается на этот факт и заключается в следующем:

  1. Для каждой вершины найдем минимальное инцидентное ей ребро.
  2. Добавим все такие рёбра в остов (это безопасно — см. лемму) и сожмем получившиеся компоненты, то есть объединим списки смежности вершин, которые эти рёбра соединяют.
  3. Повторяем шаги 1-2, пока в графе не останется только одна вершина-компонента.

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

Асимптотика

Заметим, что на каждой итерации каждая оставшаяся вершина будет задействована в «мердже». Это значит, что количество вершин-компонент уменьшится хотя бы вдвое, а значит всего итераций будет не более $O(\log n)$

На каждой итерации мы можем просматриваем почти все рёбра, так что конечное время работы составит $O(m \log n)$.

Зачем это нужно?

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

Утверждение. В случае планарных графов алгоритм работает за $O(n)$.

Доказательство. Из формулы Эйлера нам известно, что рёбер в планарном графе $O(n)$. Так как подграф планарного графа тоже всегда планарен, то после каждой итерации размер нашей задачи уменьшается в честные 2 раза — меньше становится не только вершин, но и рёбер тоже. Значит, алгоритм будет работать за $O(n) + O(\frac{n}{2}) + O(\frac{n}{4}) + \ldots = O(n)$.

Также, в отличие от алгоритмов Прима и Крускала, его можно легко распараллелить. «Параллельная сложность» у него $O(\log v)$: нужно каждую итерацию просто искать минимум по оставшимся рёбрам.

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

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

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

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

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

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

Dynamic Connectivity Problem:

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

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