Поиск минимального остовного дерева

Остовное дерево (spanning tree), или остов, связного неориентированного графа - это остовный подграф этого графа, являющийся деревом, или, другими словами, связный остовный подграф без циклов. Вес $w(T)$ остова $T$ взвешенного графа - это сумма весов его рёбер.

Пусть дан связный неориентированный граф с неотрицательными весами рёбер, и мы хотим выбрать подмножество рёбер как можно меньшего суммарного веса, с помощью которого можно было бы добраться из любой вершины в любую. Если в подмножестве рёбер есть цикл, из него всегда можно выкинуть одно из рёбер, не увеличив суммарный вес и не нарушив связности. Значит, мы хотим найти остовное дерево минимально возможного веса, или минимальное остовное дерево (minimum spanning tree).

Лемма о разрезе

Поставленную задачу мы научимся решать жадно сразу двумя способами. В основе обоих алгоритмов лежит одна и та же лемма.

Разрез (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$ не проходит через разрез $(A, B)$. Пусть $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\}$.

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

Алгоритм Прима (Jarnik, 30; Prim, 57; Dijkstra, 59) постепенно расширяет множество вершин $A$ и множество рёбер $F$, образующих дерево на $A$. Вначале $A$ состоит из одной любой вершины, $F$ пусто. На каждом шаге алгоритм находит ребро $e=(u, v)$ минимального веса, ведущее из $A$ в $V \backslash A$. Конец этого ребра $v \in V \backslash A$ алгоритм добавляет в $A$, а само ребро $e-$ к множеству $F$. При этом $F \cup\{e\}$ образует дерево на $A \cup\{v\}$.

По лемме о разрезе для множества рёбер $F$ и разреза ( $A, V \backslash A$ ) если $F$ входило в какой-то минимальный остов, то и $F \cup\{e\}$ тоже входит в какой-то минимальный остов. Когда $A=V$, рёбра $F$ образуют остовное дерево всего графа $G$, при этом $F$ входит в какое-то минимальное остовное дерево. Значит, минимальное остовное дерево состоит ровно из рёбер множества $F$.

Для того, чтобы быстро находить вершину $v$ и вес ребра $w_{e}$, для каждой вершины $u \in V$ алгоритм поддерживает вес минимального ребра, ведущего из $A$ в $u$ :

$$ d_{u}=\min \left\{w_{f}: f: a \rightarrow u, a \in A\right\} . $$

Тогда на очередном шаге $v$ - это вершина из $V \backslash A$ с минимальным значением $d_{v}$, а само $d_{v}$ - вес ребра $e$. Для перехода к следующему шагу нужно обновить значения $d_{u}$ весами рёбер, исходящих из $v$.

Получается алгоритм, практически идентичный алгоритму Дейкстры (меняются лишь приоритеты вершин). Соответственно, в зависимости от реализации, можно получить оценки времени работы $O\left(V^{2}+E\right), O((V+E) \log V)(O(V \log V+E)$ при использовании фибоначчиевой кучи).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

vector<int> d(n) # в графе n вершин
fill(d, inf)
d[0] = 0
for v = 0..(n - 1):
    q <-- (v, d[v]) # кладём в очередь вершину v с приоритетом d[v]
int W = O # сюда запишем вес минимального остова
for i = 0..(n - 1):
    v <-- q # достаём из очереди вершину с минимальным приоритетом
    W += d[v]
    for u, w in es[v]:
        if d[u] > w:
            d[u] = w
            q.decreaseKey(u, d[u]) # уменьшаем значение приоритета u до d[u]

Если нужно восстановить не только вес минимального остова, но и множество входящих в него рёбер, нужно для каждой вершины $u$ дополнительно запоминать, весу какого ребра равняется $d_{u}$.

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

Алгоритм Kраскала (Kruskal, 56) действует тоже жадно, но по-другому: он начинает с пустого множества $F$, рассматривает рёбра в порядке возрастания веса и добавляет очередное ребро $e$ в $F$, если при этом в $F$ не появится цикла.

В любой момент времени рёбра $F$ образуют лес, и, поскольку граф связен, в конце алгоритма $F$ будет образовывать остовное дерево. Из леммы о разрезе снова следует, что в любой момент времени $F$ входит в какой-то минимальный остов (на этот раз нужно в качестве разреза взять ( $A, V \backslash A$ ), где $A$ - компонента связности одного из концов ребра $e$ в графе, образованном рёбрами $F$ ).

Для реализации алгоритма Краскала нам не хватает ещё одной детали: нужно научиться быстро понимать, образуется ли цикл при добавлении ребра $e$ к множеству $F$. Цикл образуется тогда и только тогда, когда концы ребра $e$ находятся в одной компоненте связности графа, образованного рёбрами $F$. Таким образом, наша ближайшая цель научиться быстро проверять, находятся ли две вершины в одной компоненте связности (а также быстро объединять две компоненты связности в одну).

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

Система непересекающихся множеств (disjoint set union, DSU) - структура данных, позволяющая поддерживать разбиение $n$ элементов на непересекающиеся множества, а именно:

  • выдавать по элементу идентификатор множества, в котором лежит этот элемент;
  • объединять два множества в одно.

Будем считать, что элементы пронумерованы числами от 0 до $n-1$. Необходимо реализовать две функции: get (a) - функцию, возвращающую идентификатор множества, где лежит $a$ (в частности, с помощью этой функции можно проверять, лежат ли два элемента в одном множестве); а также join( $\mathrm{a}, \mathrm{b}$ ) - функцию, объединяющую множества, в которых лежат элементы $a$ и $b$. Пусть в случае, когда $a$ и $b$ лежат в одном множестве, функция join(a,b) ничего не делает.

Также будем считать, что после инициализации структуры каждое множество состоит из одного элемента и get(i) = i (если в решаемой задаче это не так, можно после инициализации объединить элементы в нужные множества с помощью функции join).

Реализация связными списками

Будем поддерживать $i d[i]$ - номер множества, в котором лежит элемент $i$, а для множества с номером $i$ будем поддерживать список его элементов elems $[i]$. Единственная хитрость: при объединении множеств сохраним для объединённого множеств идентификатор большего множества из объединяемых, тогда нужно поменять значения $i d$ лишь у элементов меньшего множества. Объединение списков же осуществляется за $O(1)$ (достаточно соединить ссылками конец одного списка и начало другого).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

init(n):
    for i = 0..(n - 1):
        id[i] = i
        elems[i] = {i}
get(i):
    return id[i]
join(a, b):
    a = id[a], b = id[b]
    if a == b:
        return
    if len(elems[a]) < len(elems[b]):
        swap (a, b)
    for x in elems[b]:
        id[x] = a
    elems[a] = concatenate(elems[a], elems[b])

При такой реализации функция get работает за $O(1)$.

Предложение

Суммарное время работы $m$ вызовов јоіп есть $O(m+n \log n)$.

Доказательство

Время работы одного вызова јоin пропорционально $O(1+x)$, где $x-$ число элементов, у которых поменялось значение $i d$. Заметим, что когда у элемента меняется значение $i d$, размер множества, в котором он находится, увеличивается хотя бы два раза. Значит значение $i d$ каждого элемента поменяется не более $\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) - это просто подъём в корень дерева, где лежит $v$, а функцию join(a, b) можно реализовать, например, подвесив корень одного дерева ребёнком к корню другого.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

init(n):
    for i = 0..(n - 1):
        p[i] = i
get(v):
    if p[v] == v:
        return v
    return get(p[v])
join(a, b):
    a = get(a), b = get(b)
    if a == b:
        return
    p[a] = b

Время работы join - это $O(1)$ плюс время работы двух запусков get. K сожалению, время работы get пока в худшем случае оценивается как $\Theta(n)$, так как высота дерева может равняться его размеру. Для улучшения оценки на время работы get применяются следующие две эвристики.

Ранговая эвристика

При объединении деревьев логично подвешивать более низкое дерево к более высокому, тогда высота будет расти медленнее. Для каждой вершины $v$ будем дополнительно хранить ещё одно значение: ранг $r k[v]$, равный высоте поддерева вершины $v$. Вначале $r k[v]=0$ для всех вершин, а при объединении деревьев будем подвешивать корень с меньшим рангом ребёнком к корню с большим рангом. При равенстве рангов неважно, какой корень к какому подвешивать, но надо увеличить ранг корня получившегося дерева на единицу.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

init(n):
    for i = 0..(n - 1):
        p[i] = i, rk[i] = 0
join(a, 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] += 1
    p[a] = b
Предложение

Для рангов вершин выполняются следующие свойства:

  1. если $v \neq p[v]$, то $r k[v] < r k[p[v]]$;
  2. вершина ранга $k$ имеет поддерево размера хотя бы $2^{k}$;
  3. количество вершин ранга $k$ не превосходит $n / 2^{k}$.
Доказательство

Первое свойство следует из того, что ранг - это высота поддерева вершины.

Заметим, что вершина ранга $k$ может появиться только при объединении двух деревьев с корнями ранга $k-1$. Отсюда по индукции следует второе свойство.

Третье свойство следует из того, что разные вершины ранга $k$ не могут иметь общих потомков.

Из третьего свойства, в частности, следует, что ранг любой вершины не превосходит $\log _{2} n$. Значит, высота любого дерева не превосходит $\log _{2} n$, и время работы функции get теперь оценивается как $O(\log n)$.

Эвристика сжатия путей

Другая идея: когда функция get(v) проходит путь к корню дерева $v$ и находит его, можно переподвесить $v$ напрямую к корню, чтобы при следующем запуске не проходить этот путь заново; структура дерева изменится, но само множество, соответствующее дереву, при этом останется прежним, поэтому такая операция корректна.

1
2
3
4
5

get(v):
    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)$.

Доказательство

Пусть $s z(v)$ - размер поддерева $v$. Назовём ребро из $v$ в $p[v]$ лёгким, если $s z(v) \leqslant s z(p[v]) / 2$, и тяжёлым иначе.

Заметим, что при выполнении get проход по каждому лёгкому ребру хотя бы удваивает размер текущего поддерева. Значит, каждый запрос get пройдёт не более чем по $\log _{2} n$ лёгким рёбрам, а суммарно проходов по лёгким рёбрам будет не более $m \log _{2} n$.

Теперь заметим, что если ребро из $v$ в $w=p[v]$ тяжёлое, и при этом $w$ не корень, то после прохода по такому ребру в запросе get размер поддерева $w$ уменьшится хотя бы в два раза. При этом у вершины, не являющейся корнем, размер поддерева может только уменьшаться. Значит, за всё время работы мы суммарно пройдём по тяжёлым рёбрам, не ведущим в корень, не более $n \log _{2} n$ раз - не более чем $\log _{2} n$ раз для каждой вершины $w$.

Осталось учесть тяжёлые рёбра, ведущие в корень; на каждый запрос get приходится не более одного такого ребра, суммарно их не более $m$.

Совместное использование эвристик

Что будет, если использовать обе эвристики одновременно? Заметим, что в этом случае ранг уже не всегда равен высоте поддерева вершины. Тем не менее, большая часть свойств остаётся верной.

Предложение

Для рангов вершин выполняются следующие свойства:

  1. если $v \neq p[v]$, то $r k[v] < r k[p[v]]$;
  2. корневая вершина ранга $k$ имеет поддерево размера хотя бы $2^{k}$;
  3. количество вершин ранга $k$ не превосходит $n / 2^{k}$.
Доказательство

Первое свойство выполняется сразу после јоin, в котором $v$ перестала быть корнем, а при переподвешивании $v$ в get разность между рангами только увеличивается.

Как и раньше, вершина ранга $k$ может появиться только при объединении двух деревьев с корнями ранга $k-1$. Отсюда по индукции следует второе свойство (но только для корневых вершин: важно, что пока вершина остаётся корнем своего дерева, размер её поддерева не уменьшается).

Третье свойство теперь тоже нужно доказывать аккуратнее: любая вершина ранга $k$ была корневой, когда получила этот ранг. В этот момент в её поддереве было хотя бы $2^{k}$ вершин, при этом ни до, ни после этого эти вершины не могли оказаться в поддереве другой вершины ранга $k$ : до этого они находились в деревьях ранга $k-1$, а после этого любой новый корень дерева, где они находятся, будет иметь ранг строго больше $k$. Значит, каждой вершине ранга $k$ соответствует множество из $2^{k}$ вершин, и эти множества не пересекаются для разных вершин ранга $k$.

Определение

Итерированный логарифм $n$ по основанию $a$

$$ \log _{a}^{*} n= \begin{cases}0, & \text { если } n \leqslant 1, \\ 1+\log _{a}^{*}\left(\log _{a} n\right), & \text { если } n>1 .\end{cases} $$

✍️ На практике можно считать, что если $n$ - число элементов, то $\log _{2}^{*} n \leqslant 5$, так как даже $\log _{2}^{*}\left(2^{65536}\right)=5$.

Теорема

При использовании обеих эвристик суммарное время работы $m$ запросов get есть $O\left(m+n \log _{2}^{*} n\right)$.

Доказательство

Ранг любой вершины в любой момент лежит в отрезке $\left[0, \log _{2} n\right]$. Покроем этот отрезок непересекающимися отрезками вида $\left[k+1,2^{k}\right]$ (а также отрезком $[0,0]$ ):

$$ \{0\},\{1\},\{2\},\{3,4\},\left\{5,6, \ldots, 2^{4}=16\right\},\left\{17,18, \ldots, 2^{16}=65536\right\}, \ldots $$

Всего таких отрезков будет не более $\log _{2}^{*} n+1$. Пронумеруем эти отрезки. Назовём крутостью $c_{v}$ ребра из $v$ в $p[v]$ разность номеров отрезков, в которые попадают $r k[p[v]]$ и $r k[v]$. Так, крутость ребра из вершины ранга 5 в вершину ранга 13 равна нулю; крутость ребра из вершины ранга 4 в вершину ранга 65538 равна трём. Крутость любого ребра не превосходит $\log _{2}^{*} n$. Поскольку разность рангов родителя вершины и самой вершины в ходе алгоритма может только возрастать, крутость ребра из вершины в её родителя тоже может только возрастать.

Время работы $i$-го запроса get пропорционально числу пройденных по пути к корню рёбер. Поделим эти рёбра на несколько типов: отдельно посчитаем ребро, ведущее в корень дерева, и ближайшее к корню ребро положительной крутости (возможно, эти два ребра совпадают). Пусть помимо этих рёбер на пути было ещё $a_{i}$ рёбер положительной крутости (назовём их $a$-рёбрами) и $b_{i}$ рёбер нулевой крутости (назовём их $b$-рёбрами). Тогда при выполнении $i$-го запроса get было посещено не более $2+a_{i}+b_{i}$ рёбер.

Пусть ребро из $v$ в $p[v]$ - одно из $a$-рёбер. Поскольку на пути в корень было ещё хотя бы одно ребро положительной крутости, крутость $c_{v}$ после переподвешивания вершины $v$ строго возрастёт. Значит, из каждой вершины $v$ мы могли подняться по $a$-ребру за всё время работы не более $\log _{2}^{*} n$ раз, то есть $\sum_{i} a_{i} \leqslant n \log _{2}^{*} n$.

Теперь пусть ребро из $v$ в $p[v]$ - одно из $b$-рёбер. После переподвешивания $v$ разность рангов $r k[p[v]]-r k[v]$ возросла хотя бы на единицу. Пусть $r k[v]$ находится в отрезке $\left[k+1,2^{k}\right]$, тогда подъёмов из вершины $v$ по $b$-ребру было не более $2^{k}$ за всё время работы (после $2^{k}$ подъёмов $r k[p[v]]$ уже точно будет находиться в следующем отрезке, то есть ребро в родителя будет иметь положительную крутость). Заметим, что вершин с рангом в отрезке $\left[k+1,2^{k}\right]$ всего не более

$$ \frac{n}{2^{k+1}}+\frac{n}{2^{k+2}}+\cdots \leqslant \frac{n}{2^{k}} $$

значит, проходов по $b$-рёбрам из вершин с рангом в отрезке $\left[k+1,2^{k}\right]$ за всё время было не более $2^{k} \cdot n / 2^{k}=n$. Тогда всего проходов по $b$-рёбрам было не более $n \log _{2}^{*} n$.

Итак, суммарное время работы $m$ запросов get есть

$$ O\left(\sum_{i=1}^{m} 2+a_{i}+b_{i}\right)=O\left(2 m+n \log _{2}^{*} n+n \log _{2}^{*} n\right)=O\left(m+n \log _{2}^{*} n\right) $$

✍️ Можно показать, что суммарное время работы $m$ запросов get не превосходит $O(m \cdot \alpha(n))$, где $\alpha(n)$ - обратная функция Аккермана, растущая ещё медленнее, чем итерированный логарифм.

Возвращаясь к алгоритму Краскала

1
2
3
4
5
6

sort(es) # сортируем рёбра по возрастанию веса
init(n) # инициализируем DSU
for e in es: # ребро из e.а в e.b веса e.w
    if get(e.a) != get(e.b):
        join(e.a, e.b)
        mst.push_back(e)# добавляем ребро к ответу

При использовании обеих эвристик получаем время работы $O\left(E \log V+E+V \log _{2}^{*} V\right)$ (или $O(E \log V+E \cdot \alpha(V))$ ). В случае, когда рёбра уже даны в порядке возрастания веса, либо когда из-за особенностей задачи рёбра можно отсортировать быстрее, чем за $O(E \log V)$, реализация DSU деревьями позволяет улучшить эффективность алгоритма.

✍️ Помимо изученных нами алгоритмов, известен рандомизированный алгоритм поиска минимального остова с линейным математическим ожиданием временем работы (Karger, Klein, Tarjan, 1995), а также алгоритм с временем работы $O(E \cdot \alpha(E, V))$ (Chazelle, 2000), где $\alpha$ - двупараметрическая версия обратной функции Аккермана (которая тоже растёт очень медленно).