Рассмотрим следующую задачу:
Авиакомпания содержит \(m\) рейсов между \(n\) городами, \(i\)-ый из них обходится в \(w_i\) рублей, причём из любого города можно добраться до любого другого. В стране наступил кризис, и нужно отказаться от как можно большего числа из них таким образом, что содержание оставшиъся рейсов будет наиболее дешевым.
Иными словами, нужно найти дерево минимального веса, которое является подграфом данного неориентированного графа. Такие деревья называют остовами (каркас, скелет; ударение на первый слог, но так мало кто произносит). По-английски — minimum spanning tree (дословно, минимальное покрывающее дерево).
Почему дерево? Потому что в противном случае там был бы цикл, из которого можно удалить какое-то ребро и получить более оптималный ответ. А если это больше, чем одно дерево, то какие-то две вершины остаются несвязны.
Вообще, следующие утверждения про деревья являются эквивалентными:
Назовем подграф \(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\), но имеющее не меньший вес.
Алгоритм Борувки опирается на этот факт и заключается в следующем:
Алгоритм может работать неправильно, если в графе есть ребра, равные по весу. Пример: «треугольник» с одинаковыми весами рёбер. Избежать это можно введя какой-то дополнительный порядок на рёбрах — например, сравнивая пары из веса и номера ребра.
Заметим, что на каждой итерации каждая оставшаяся вершина будет задействована в «мердже». Это значит, что количество вершин-компонент уменьшится хотя бы вдвое, а значит всего итераций будет не более \(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 можете почитать в этом посте.