Построение минимального остовного дерева (MST)

1 Постановка задачи

Пусть задан связный неориентированный граф [math]G = (V, E)[/math] с весами рёбер [math]f(e)[/math]. Подграф, являющийся деревом и проходящий через все вершины [math]G[/math], называется основным деревом. Остовное дерево называется минимальным, если суммарный вес его рёбер является минимальным среди всех остовных деревьев.

Постановка задачи и алгоритм её решения были впервые опубликованы в работе Отакара Борувки. Английское название задачи – Minimum Spanning Tree (MST).

2 Варианты задачи

Если исходный граф [math]G[/math] несвязный, то набор минимальных остовных деревьев для всех компонент связности называется минимальным остовным лесом (Minimum Spanning Forest, MSF).

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

В распределённой задаче может присутствовать дополнительное требование, что обмен данными происходит только вдоль рёбер графа.

3 Свойства задачи

Веса. Решение задачи зависит не от значений весов, а от их порядка. Таким образом, вместо задания весов можно задать порядок – предикат «меньше или равно» на множестве пар рёбер графа. По этой причине можно без ограничения общности считать, что все веса рёбер различны – для этого следует упорядочить рёбра вначале по весу, а затем по номеру. Кроме того, к исходным весам можно применить любую возрастающую функцию и это не приведёт к изменению решения. Как следствие, можно считать, что все веса находятся в заданном интервале, например, [math][0, 1][/math].

Существование и единственность. Минимальный опорный лес всегда существует, а если все веса рёбер различны, то он единственный. Как уже отмечалось, всегда можно сделать веса рёбер различными. Если условие различных весов не выполняется, легко построить пример, в котором будет существовать более одного минимального остовного дерева.

Схлопывание фрагментов. Пусть [math]F[/math] – фрагмент минимального остовного дерева графа [math]G[/math], а граф [math]G'[/math] получен из [math]G[/math] склеиванием вершин, принадлежащих [math]F[/math]. Тогда объединение [math]F[/math] и минимального остовного дерева графа [math]G'[/math] даёт минимальное остовное дерево исходного графа [math]G[/math].

Минимальное ребро фрагмента. Пусть [math]F[/math] – фрагмент минимального остовного дерева и [math]e_F[/math] – ребро наименьшего веса, исходящее из [math]F[/math] (т.е. ровно один его конец является вершиной из [math]F[/math]). Если ребро [math]e_F[/math] единственно, то оно принадлежит минимальному остовному дереву. На этом свойстве основаны алгоритм Борувки и алгоритм Прима.

Минимальное ребро графа. Если [math]e^*[/math] – единственное ребро графа с минимальным весом, то оно принадлежит минимальному остовному дереву. На этом свойстве основан алгоритм Крускала.

Ассоциативность по рёбрам. Пусть [math]MSF(E)[/math] – минимальный остовный лес графа с рёбрами [math]E[/math]. Тогда

[math] MSF(E_1 \cup E_2 \cup \dots \cup E_k) = MSF(MSF(E_1) \cup MSF(E_2) \cup \dots \cup MSF(E_k)). [/math]

Количество рёбер остовного леса для графа с [math]n[/math] вершинами и [math]c[/math] компонентами связности равно [math]n-c[/math]. Это свойство может использоваться для более быстрого завершения работы алгоритмов, если число компонент связности известно заранее.

4 Описание входных и выходных данных

Входные данные: взвешенный граф [math](V, E, W)[/math] ([math]n[/math] вершин [math]v_i[/math] и [math]m[/math] рёбер [math]e_j = (v^{(1)}_{j}, v^{(2)}_{j})[/math] с весами [math]f_j[/math]).

Объём входных данных: [math]O(m + n)[/math].

Выходные данные: список рёбер минимального остовного дерева (для несвязного графа – список минимальных остовных деревьев для всех компонент связности).

Объём выходных данных: [math]O(n)[/math].

5 Алгоритмы решения задачи

Существует три классических подхода к решению задачи:

• Алгоритм Борувки;
• Алгоритм Крускала;
• Алгоритм Прима.

Во всех случаях последовательная сложность алгоритма [math]O(m \ln n)[/math] при использовании обычных структур данных. (Обозначения: [math]m[/math] – число рёбер, [math]n[/math] – число вершин.)

Все другие алгоритмы, как правило, являются вариацией на тему одного из трёх перечисленных, или их комбинацией.

• Алгоритм GHS (Gallager, Humblet, Spira) и его последующие версии являются распределённым вариантом алгоритма Борувки. Это алгоритм обычно используется для автоматического распределённого построения остовного дерева сетью коммутаторов.
• Алгоритм Габова и др. использует фибоначчиеву кучу для упорядочения рёбер в алгоритме Борувки. Сложность [math]O(m \ln \beta (m, n))[/math].
• Алгоритм Фредмана и Уилларда предназначен для графов с целочисленными весами и имеет линейную оценку сложности [math]O(m)[/math]. Используется алгоритм Прима в сочетании со специально разработанным алгоритмом кучи (AF-heap).
• Алгоритм Каргера и др. решает задачу в среднем за линейное время [math]O(m)[/math]. (Существование детерминированного алгоритма с линейной оценкой сложности является открытым вопросом.)

Следует отметить, что алгоритмы, имеющие асимптотическую сложность лучшую, чем [math]O(m \ln n)[/math], как правило, на практике работают медленнее классических алгоритмов: константа в оценке настолько велика, что выигрыш от лучшей асимптотике будет заметен только на графах очень больших размеров.

6 Ресурс параллелизма

1. Свойства схлопывания фрагментов и минимального ребра фрагмента позволяют обрабатывать фрагменты независимо. Основанный на этих свойствах алгоритм Борувки обладает наибольшим ресурсом параллелизма среди трёх классических алгоритмов.
2. Ассоциативность по рёбрам может быть использована для параллелизации алгоритмов Крускала и Прима, которые изначально являются существенно последовательными.
3. Использование параллельных алгоритмов сортировки рёбер графа, либо параллельная сортировка рёбер у каждой вершины или у каждого фрагмента.