Остовное дерево (spanning tree), или остов, связного неориентированного графа $G=(V,E)$ — это связный остовный подграф без циклов (то есть дерево на всех вершинах $V$). Вес $w(T)$ остова $T$ взвешенного графа — это сумма весов его рёбер. Минимальное остовное дерево (minimum spanning tree, MST) — остов минимального суммарного веса.
Пусть дан связный неориентированный граф с неотрицательными весами рёбер. Мы хотим выбрать подмножество рёбер минимального суммарного веса, с помощью которого можно добраться из любой вершины в любую. Если в подмножестве рёбер есть цикл, из него всегда можно выкинуть одно ребро, не увеличив суммарный вес и не нарушив связности. Значит, мы ищем именно минимальное остовное дерево.
Сводка алгоритмов
Алгоритм
Структура данных
Время работы
Прима (наивный)
Массив
$O(V^2 + E)$
Прима
Двоичная куча
$O((V+E)\log V)$
Прима
Фибоначчиева куча
$O(V \log V + E)$
Краскала + DSU (списки)
DSU на списках
$O(E \log V)$
Краскала + DSU (деревья)
DSU с эвристиками
$O(E \log V + E \cdot \alpha(V))$
Лемма о разрезе
Поставленную задачу мы научимся решать жадно сразу двумя способами. В основе обоих алгоритмов лежит одна и та же лемма.
Определение
Разрез (cut) $(A, B)$ графа $G=(V, E)$ — это разбиение множества вершин на два непустых непересекающихся множества: $A \cup B=V$, $A \cap B=\emptyset$. Ребро $e$ проходит через разрез $(A, B)$, если оно соединяет вершину из $A$ с вершиной из $B$.
Лемма о разрезе
Пусть множество рёбер $F \subset E$ входит в некоторый минимальный остов графа $G=(V, E)$. Пусть $(A, B)$ — разрез $G$, причём ни одно ребро из $F$ не проходит через этот разрез. Пусть $e$ — ребро с наименьшим весом из всех, проходящих через разрез $(A, B)$. Тогда $F \cup\{e\}$ входит в некоторый минимальный остов графа $G$.
Доказательство
Пусть $T=\left(V, E^{\prime}\right)$ — минимальный остов, содержащий $F$. Если $e$ тоже лежит в $T$, то доказывать нечего. Иначе рассмотрим граф $T^{\prime}=\left(V, E^{\prime} \cup\{e\}\right)$. В $T^{\prime}$ найдётся цикл, проходящий через ребро $e$; на этом цикле найдётся ещё хотя бы одно проходящее через разрез $(A, B)$ ребро $e^{\prime}$. При этом $w_{e} \leqslant w_{e^{\prime}}$. Тогда $T^{\prime \prime}=\left(V, E^{\prime} \cup\{e\} \backslash\left\{e^{\prime}\right\}\right)$ — остов, при этом $w\left(T^{\prime \prime}\right) \leqslant w(T)$, и $T^{\prime \prime}$ содержит $F \cup\{e\}$.
Алгоритм Прима
Алгоритм Прима (Jarník, 1930; Prim, 1957; Dijkstra, 1959) постепенно расширяет множество вершин $A$ и множество рёбер $F$, образующих дерево на $A$. Вначале $A$ состоит из одной любой вершины, $F$ пусто. На каждом шаге алгоритм находит ребро $e=(u, v)$ минимального веса, ведущее из $A$ в $V \backslash A$. Конец этого ребра $v \in V \backslash A$ добавляется в $A$, а само ребро $e$ — к множеству $F$.
По лемме о разрезе для разреза $(A, V \backslash A)$: если $F$ входило в какой-то минимальный остов, то и $F \cup\{e\}$ тоже входит в какой-то минимальный остов. Когда $A=V$, рёбра $F$ образуют минимальное остовное дерево.
Для того чтобы быстро находить очередное ребро, для каждой вершины $u \in V \setminus A$ поддерживается:
$$
d_{u}=\min \left\{w_f : f = (a, u),\; a \in A\right\}.
$$
Тогда на очередном шаге $v$ — это вершина из $V \backslash A$ с минимальным $d_{v}$. Для перехода к следующему шагу обновляем $d_{u}$ весами рёбер, исходящих из $v$. Алгоритм практически идентичен алгоритму Дейкстры; соответственно, оценки времени работы аналогичны: $O\left(V^{2}+E\right)$ или $O((V+E) \log V)$.
#include<queue>#include<vector>#include<climits>usingnamespace std;
// graph[v] = {(w, u), ...} — список смежности взвешенного графа
// Возвращает вес минимального остова
intprim(vector<vector<pair<int,int>>>& g, int n) {
vector<int> d(n, INT_MAX);
vector<bool> inMST(n, false);
d[0] =0;
using P = pair<int, int>; // (d[v], v)
priority_queue<P, vector<P>, greater<P>> pq;
pq.push({0, 0});
int W =0;
while (!pq.empty()) {
auto [dv, v] = pq.top(); pq.pop();
if (inMST[v]) continue;
inMST[v] = true;
W += d[v];
for (auto [w, u] : g[v]) {
if (d[u] > w) {
d[u] = w;
pq.push({d[u], u});
}
}
}
return W;
}
Свойства
Если нужно восстановить не только вес минимального остова, но и множество входящих в него рёбер, нужно для каждой вершины $u$ дополнительно запоминать, весу какого ребра равняется $d_u$.
Алгоритм Краскала
Алгоритм Краскала (Kruskal, 1956) действует тоже жадно, но по-другому: он начинает с пустого множества $F$, рассматривает рёбра в порядке возрастания веса и добавляет очередное ребро $e$ в $F$, если при этом в $F$ не появится цикла.
В любой момент времени рёбра $F$ образуют лес; поскольку граф связен, в конце алгоритма $F$ образует остовное дерево. Из леммы о разрезе следует, что в любой момент времени $F$ входит в какой-то минимальный остов (в качестве разреза берётся $(A, V \backslash A)$, где $A$ — компонента связности одного из концов ребра $e$ в лесу $F$).
Для реализации нужно быстро проверять, образует ли добавление ребра $e$ цикл, то есть находятся ли оба конца $e$ в одной компоненте связности леса $F$. Для этого используется структура данных DSU.
Система непересекающихся множеств
Определение
Система непересекающихся множеств (disjoint set union, DSU) — структура данных, поддерживающая разбиение $n$ элементов на непересекающиеся множества и операции:
join(a, b) — объединение множеств, содержащих $a$ и $b$.
Будем считать, что элементы пронумерованы числами от $0$ до $n-1$. После инициализации каждое множество состоит из одного элемента и get(i) = i.
Реализация связными списками
Будем поддерживать $\mathit{id}[i]$ — номер множества, содержащего элемент $i$, а для множества с номером $i$ — список его элементов $\mathit{elems}[i]$. При объединении сохраняем идентификатор большего множества: тогда нужно менять $\mathit{id}$ лишь у элементов меньшего множества. Объединение списков осуществляется за $O(1)$.
id_: list[int] = []
elems: list[list[int]] = []
definit(n: int):
global id_, elems
id_ = list(range(n))
elems = [[i] for i in range(n)]
defget(i: int) -> int:
return id_[i]
defjoin(a: int, b: int):
a, b = id_[a], id_[b]
if a == b:
returnif len(elems[a]) < len(elems[b]):
a, b = b, a
for x in elems[b]:
id_[x] = a
elems[a].extend(elems[b])
elems[b].clear()
#include<vector>#include<list>usingnamespace std;
vector<int> id_;
vector<list<int>> elems;
voidinit(int n) {
id_.resize(n);
elems.resize(n);
for (int i =0; i < n; i++) {
id_[i] = i;
elems[i] = {i};
}
}
intget(int i) { return id_[i]; }
voidjoin(int a, int b) {
a = id_[a]; b = id_[b];
if (a == b) return;
if (elems[a].size() < elems[b].size()) swap(a, b);
for (int x : elems[b]) id_[x] = a;
elems[a].splice(elems[a].end(), elems[b]);
}
При такой реализации функция get работает за $O(1)$.
Предложение
Суммарное время работы $m$ вызовов join есть $O(m + n \log n)$.
Доказательство
Время работы одного вызова join пропорционально $O(1+x)$, где $x$ — число элементов, у которых поменялось значение $\mathit{id}$. Заметим, что когда у элемента меняется значение $\mathit{id}$, размер множества, в котором он находится, увеличивается хотя бы в два раза. Значит, значение $\mathit{id}$ каждого элемента поменяется не более $\log_2 n$ раз.
Заметим, что такая реализация DSU уже позволяет реализовать алгоритм Краскала за время $O(E \log E + E + E \log V) = O(E \log V)$: первое слагаемое — сортировка рёбер по весу — мажорирует время работы последующих шагов.
Свойства
$O(E \log E)=O(E \log V)$, так как $E \leqslant V^{2}$, если в графе нет кратных рёбер (а если они есть, от них можно предварительно избавиться, оставив лишь самое лёгкое ребро между каждой парой вершин).
Тем не менее, мы изучим ещё одну реализацию DSU, которая даёт лучшую амортизированную оценку времени работы операций.
Реализация деревьями
Каждое множество будем хранить в виде подвешенного дерева. Для каждого элемента $v$ хранится ссылка $p[v]$ на родителя; для корня $p[v]=v$. Идентификатор множества — корень дерева.
Функция get(v) — подъём в корень; join(a, b) — подвешивание корня одного дерева к корню другого.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
p: list[int] = []
definit(n: int):
global p
p = list(range(n))
defget(v: int) -> int:
if p[v] == v:
return v
return get(p[v])
defjoin(a: int, b: int):
a, b = get(a), get(b)
if a == b:
return p[a] = b
#include<vector>#include<numeric>usingnamespace std;
vector<int> p;
voidinit(int n) {
p.resize(n);
iota(p.begin(), p.end(), 0);
}
intget(int v) {
if (p[v] == v) return v;
return get(p[v]);
}
voidjoin(int a, int b) {
a = get(a); b = get(b);
if (a == b) return;
p[a] = b;
}
Время работы join — это $O(1)$ плюс время работы двух запусков get. В худшем случае высота дерева равна его размеру, и get работает за $\Theta(n)$. Для улучшения применяются две эвристики.
Ранговая эвристика
При объединении деревьев логично подвешивать более низкое дерево к более высокому. Для каждой вершины $v$ хранится ранг $\mathit{rk}[v]$ — высота поддерева вершины $v$. При равенстве рангов ранг корня нового дерева увеличивается на единицу.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
p: list[int] = []
rk: list[int] = []
definit(n: int):
global p, rk
p = list(range(n))
rk = [0] * n
# get(v) — без измененийdefjoin(a: int, b: int):
a, b = get(a), get(b)
if a == b:
returnif rk[a] > rk[b]:
a, b = b, a
if rk[a] == rk[b]:
rk[b] +=1 p[a] = b
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> p, rk;
voidinit(int n) {
p.resize(n); rk.assign(n, 0);
iota(p.begin(), p.end(), 0);
}
// get(v) — без изменений
voidjoin(int a, int b) {
a = get(a); b = get(b);
if (a == b) return;
if (rk[a] > rk[b]) swap(a, b);
if (rk[a] == rk[b]) rk[b]++;
p[a] = b;
}
Предложение
Для рангов вершин выполняются следующие свойства:
если $v \neq p[v]$, то $\mathit{rk}[v] < \mathit{rk}[p[v]]$;
вершина ранга $k$ имеет поддерево размера хотя бы $2^{k}$;
количество вершин ранга $k$ не превосходит $n / 2^{k}$.
Доказательство
Первое свойство следует из того, что ранг — это высота поддерева вершины.
Заметим, что вершина ранга $k$ может появиться только при объединении двух деревьев с корнями ранга $k-1$. Отсюда по индукции следует второе свойство.
Третье свойство следует из того, что разные вершины ранга $k$ не могут иметь общих потомков.
Из третьего свойства следует, что ранг любой вершины не превосходит $\log_2 n$. Значит, высота любого дерева не превосходит $\log_2 n$, и get работает за $O(\log n)$.
Эвристика сжатия путей
Когда get(v) находит корень, можно переподвесить $v$ напрямую к корню — при следующем запросе путь будет короче.
1
2
3
4
5
defget(v: int) -> int:
if p[v] == v:
return v
p[v] = get(p[v])
return p[v]
Если использовать эвристику сжатия путей без ранговой эвристики, то тоже можно получить оценку времени работы get $O(\log n)$, но уже амортизированную.
Предложение
При использовании эвристики сжатия путей без ранговой эвристики $m$ запросов get имеют суммарное время работы $O(m + (m+n)\log n)$.
Доказательство
Пусть $\mathit{sz}(v)$ — размер поддерева $v$. Назовём ребро из $v$ в $p[v]$ лёгким, если $\mathit{sz}(v) \leqslant \mathit{sz}(p[v]) / 2$, и тяжёлым иначе.
При выполнении get проход по каждому лёгкому ребру хотя бы удваивает размер текущего поддерева. Значит, каждый запрос get пройдёт не более $\log_2 n$ лёгких рёбер, а суммарно проходов по лёгким рёбрам будет не более $m \log_2 n$.
Теперь заметим, что если ребро из $v$ в $w=p[v]$ тяжёлое, и при этом $w$ не корень, то после прохода по такому ребру в запросе get размер поддерева $w$ уменьшится хотя бы в два раза. При этом у вершины, не являющейся корнем, размер поддерева может только уменьшаться. Значит, за всё время работы мы суммарно пройдём по тяжёлым рёбрам, не ведущим в корень, не более $n \log_2 n$ раз.
Осталось учесть тяжёлые рёбра, ведущие в корень; на каждый запрос get приходится не более одного такого ребра, суммарно их не более $m$.
Совместное использование эвристик
При использовании обеих эвристик ранг уже не всегда равен высоте поддерева вершины. Тем не менее, большая часть свойств остаётся верной.
Предложение
При совместном использовании эвристик для рангов выполняются те же свойства 1–3, что и при использовании только ранговой эвристики.
Доказательство
Первое свойство выполняется сразу после join, в котором $v$ перестала быть корнем, а при переподвешивании $v$ в get разность между рангами только увеличивается.
Как и раньше, вершина ранга $k$ может появиться только при объединении двух деревьев с корнями ранга $k-1$. Отсюда по индукции следует второе свойство (но только для корневых вершин).
Третье свойство: любая вершина ранга $k$ была корневой, когда получила этот ранг. В этот момент в её поддереве было хотя бы $2^{k}$ вершин, при этом ни до, ни после этого эти вершины не могли оказаться в поддереве другой вершины ранга $k$. Значит, каждой вершине ранга $k$ соответствует множество из $2^{k}$ вершин, и эти множества не пересекаются.
Определение
Итерированный логарифм $n$ по основанию $a$:
$$\log_a^* n = \begin{cases}0, & \text{если } n \leqslant 1, \\ 1 + \log_a^*(\log_a n), & \text{если } n > 1.\end{cases}$$
На практике можно считать, что $\log_2^* n \leqslant 5$, так как даже $\log_2^*(2^{65536}) = 5$.
Теорема
При использовании обеих эвристик суммарное время работы $m$ запросов get есть $O(m + n \log_2^* n)$.
Доказательство
Ранг любой вершины в любой момент лежит в отрезке $[0, \log_2 n]$. Покроем этот отрезок непересекающимися отрезками вида $[k+1, 2^k]$ (а также $[0, 0]$):
Всего таких отрезков будет не более $\log_2^* n + 1$.
Назовём крутостью $c_v$ ребра из $v$ в $p[v]$ разность номеров отрезков, в которые попадают $\mathit{rk}[p[v]]$ и $\mathit{rk}[v]$. Крутость любого ребра не превосходит $\log_2^* n$; крутость ребра из вершины в её родителя может только возрастать.
Время работы $i$-го запроса get пропорционально числу пройденных рёбер. Из числа не ведущих в корень рёбер выделим $a$-рёбра (положительная крутость, не ближайшее к корню) и $b$-рёбра (нулевая крутость). Посещено не более $2 + a_i + b_i$ рёбер.
Из $a$-ребра из $v$: после переподвешивания $c_v$ строго возрастёт. Значит, каждую вершину $v$ мы поднимали по $a$-ребру не более $\log_2^* n$ раз; итого $\sum_i a_i \leqslant n \log_2^* n$.
Из $b$-ребра из $v$ с рангом в $[k+1, 2^k]$: после переподвешивания $\mathit{rk}[p[v]]$ увеличивается. Подъёмов из $v$ по $b$-ребру не более $2^k$ за всё время. Вершин с рангом в $[k+1, 2^k]$ не более $n / 2^k$, значит проходов по $b$-рёбрам из таких вершин не более $2^k \cdot n/2^k = n$. Суммарно по всем отрезкам: $\sum_i b_i \leqslant n \log_2^* n$.
Можно показать, что суммарное время работы $m$ запросов get не превосходит $O(m \cdot \alpha(n))$, где $\alpha(n)$ — обратная функция Аккермана, растущая ещё медленнее, чем итерированный логарифм.
Возвращаясь к алгоритму Краскала
1
2
3
4
5
6
7
8
9
10
11
12
13
14
defkruskal(edges: list[tuple[int, int, int]], n: int) -> list[tuple[int, int, int]]:
"""
edges: список рёбер (a, b, w)
n: число вершин
Возвращает рёбра минимального остова.
""" edges.sort(key=lambda e: e[2]) # сортируем по весу init(n)
mst = []
for a, b, w in edges:
if get(a) != get(b):
join(a, b)
mst.append((a, b, w))
return mst
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<algorithm>#include<vector>usingnamespace std;
structEdge { int a, b, w; };
vector<Edge> kruskal(vector<Edge>& edges, int n) {
sort(edges.begin(), edges.end(),
[](const Edge& x, const Edge& y){ return x.w < y.w; });
init(n);
vector<Edge> mst;
for (auto& e : edges) {
if (get(e.a) != get(e.b)) {
join(e.a, e.b);
mst.push_back(e);
}
}
return mst;
}
При использовании обеих эвристик получаем время работы $O(E \log V + E \cdot \alpha(V))$. В случае, когда рёбра уже отсортированы по весу, реализация DSU деревьями позволяет улучшить эффективность алгоритма.
Свойства
Помимо изученных нами алгоритмов, известен рандомизированный алгоритм поиска минимального остова с линейным ожидаемым временем работы (Karger, Klein, Tarjan, 1995), а также алгоритм с временем работы $O(E \cdot \alpha(E, V))$ (Chazelle, 2000), где $\alpha$ — двупараметрическая версия обратной функции Аккермана.