Минимальным остовным деревом (МОД) связного взвешенного графа называется его связный подграф, состоящий из всех вершин исходного дерева и некоторых его ребер, причем сумма весов ребер минимально возможная. Если исходный граф несвязен, то описываемую ниже процедуру можно применять поочередно к каждой его компоненте связности, получая тем самым минимальные остовные деревья для этих компонент[7].
МОД для связного графа можно найти с помощью грубой силы. Поскольку множество ребер МОД является подмножеством в множестве ребер исходного графа, можно просто перебрать все возможные подмножества и найти среди них МОД. Нетрудно видеть, что это чрезвычайно трудоемкий процесс. В множестве из N ребер имеется 2N подмножеств. Для каждого из этих подмножеств мы должны будем проверить, что оно задает связный подграф, охватывающий все вершины исходного, и не содержит циклов, а затем сосчитать его вес. Процесс можно ускорить после того, как найдено первое остовное дерево. Никакое подмножество ребер, полный вес которого больше, чем у уже найденного наилучшего остовного дерева, не может нам подойти, поэтому нет необходимости проверять связность, ацикличность и охват всех вершин. Однако даже и при этом улучшении сложность метода грубой силы будет порядка O(2N).
Алгоритм Дейкстры-Прима
В конце 1950-х годов Эдгар Дейкстра и Прим, работая и публикуя свои результаты независимо друг от друга, предложили следующий алгоритм построения МОД[7].
Воспользуемся для поиска МОД так называемым жадным алгоритмом. Жадные алгоритмы действуют, используя в каждый момент лишь часть исходных данных и принимая лучшее решение на основе этой части. В нашем случае мы будем на каждом шаге рассматривать множество ребер, допускающих присоединение к уже построенной части остовного дерева, и выбирать из них ребро с наименьшим весом. Повторяя эту процедуру, мы получим остовное дерево с наименьшим весом.
Разобьем вершины графа на три класса: вершины, вошедшие в уже построенную часть дерева, вершины, окаймляющие построенную часть, и еще не рассмотренные вершины. Начнем с произвольной вершины графа и включим ее в остовное дерево. Поскольку результатом построения будет некорневое дерево, выбор исходной вершины не влияет на окончательный результат (конечно, если МОД единственно). Все вершины, соединенные с данной, заносим в кайму. Затем выполняется цикл поиска ребра с наименьшим весом, соединяющего уже построенную часть остовного дерева с каймой; это ребро вместе с новой вершиной добавляется в дерево и происходит обновление каймы. После того, как в дерево попадут все вершины, работа будет закончена.
Вот как выглядит алгоритм:
1. Выбрать начальный узел
2. Сформировать начальную кайму, состоящую из вершин, соседних с начальным узлом
3.while в графе есть вершины, не попавшие в дерево do
4. Выбрать ребро из дерева в кайму с наименьшим весом
5. Добавить конец ребра к дереву
6. Изменить кайму, для чего
7. Добавить в кайму вершины, соседние с новой
8.Обновить список ребер из дерева в кайму так, чтобы он состоял из ребер наименьшего веса
End while
На рисунке 55 описано исполнение алгоритма на конкретном примере. В начале процесса мы выбираем произвольный узел A. Как мы уже говорили, при другом выборе начальной вершины результат будет тем же самым, если МОД единственно. Исходный граф изображен на рис. 55 (а) и, как уже упоминалось, мы начинаем построение МОД с вершины A. Все вершины, непосредственно связанные с A, образуют исходную кайму. Видно, что ребро наименьшего веса связывает узлы A и B, поэтому к уже построенной части МОД добавляется вершина B вместе с ребром AB. При добавлении к дереву вершины B (рис. 55 (в)) мы должны определить, не следует ли добавить к кайме новые вершины. В результате мы обнаруживаем, что это необходимо проделать с вершинами E и G. Поскольку обе эти вершины соединены только с вершиной B уже построенной части дерева, мы добавляем соединяющие ребра к списку рассматриваемых на следующем шаге. Здесь же необходимо проверить, являются ли ребра, ведущие из вершины A в C, D и F, кратчайшими среди ребер, соединяющих эти вершины с деревом, или есть более удобные ребра, исходящие из B. В исходном графе вершина B не соединена непосредственно ни с C, ни с F, поэтому для них ничего не меняется. А вот ребро BD короче ребра AD, и поэтому должно его заменить. Наименьший вес из пяти ребер, идущих в кайму, имеет ребро BE, поэтому к дереву нужно добавить его и вершину E (рис. 55 (г)). Вес ребра EG меньше веса ребра BG, поэтому оно замещает последнее. Из четырех ребер, ведущих в кайму, наименьший вес имеет AC, поэтому следующим к дереву добавляется оно. Добавление к остовному дереву вершины C и ребра AC (рис. 55 (д)) не приводит к изменению списка ребер.
Затем мы выбираем ребро AF и добавляем его к дереву вместе с вершиной F. Кроме того, мы меняем список связей, поскольку вес ребра FD меньше веса ребра BD, а вес ребра FG меньше веса ребра EG. В получившейся кайме (рис. 55 (е)) ребро FD имеет наименьший вес среди оставшихся, и оно добавляется следующим.
Теперь осталось добавить к дереву всего один узел (рис. 55 (ж)). После этого процесс завершается, и мы построили МОД с корнем в вершине A (рис. 55 (з)).
Рис. 55. Принцип работы алгоритма Дейкстры-Примы
Алгоритм Крускала
Алгоритм Дейкстры-Прима начинает построение МОД с конкретной вершины графа и постепенно расширяет построенную часть дерева; в отличие от него алгоритм Крускала делает упор на ребрах графа[7].
В этом алгоритме мы начинаем с пустого дерева и добавляем к нему ребра в порядке возрастания их весов пока не получим набор ребер, объединяющий все вершины графа. Если ребра закончатся до того, как все вершины будут соединены между собой, то это означает, что исходный граф был несвязным, и полученный нами результат представляет собой объединение МОД всех его компонент связности.
Мы работаем с тем же графом (см. рис. 56 (а)), что и при описании алгоритма Дейкстры Прима. Начнем с ребра наименьшего веса, то есть с ребра DF.
Начальная ситуация изображена на рис. 56 (б).
Следующим добавляется ребро веса 56, соединяющее вершины A и B (рис. 56 (в)), а затем — ребро веса три, и мы получаемситуацию с рис. 56 (г).
К результирующему графу последовательно добавляются ребра весов 4 и 5 (рисунки 56 (д) и (е)). Несоединенной осталась лишь вершина G. Следующими мы должны рассмотреть ребра веса. Два из четырех ребер веса 6 следует отбросить, поскольку их добавление приведет к появлению цикла в уже построенной части МОД. Присоединение ребра CF создало бы цикл, содержащий вершину A, а присоединение ребра BD — цикл, содержащий вершины A и F. Обе оставшиеся возможности подходят в равной степени, и, выбирая одну из них, мы получаем либо МОД с рис. 56 (ж), либо МОД с рис. 56 (з).
Рис.56. Принцип работы алгоритма Крускала
Вот общий алгоритм, реализующий эту процедуру (число ребер в графе обозначено через E, а число вершин — через N):
1. Отсортировать ребра в порядке возрастания весов
2. Инициализировать структуру разбиений
edgeCount = 1
while edgeCount
parent1 = FindRoot(edge[edgeCount].start)
parent2 = FindRoot(edge[edgeCount].end)
if parent1 = parent2 then
добавить edge[edgeCount] в остовное дерево
includedCount = 1
Union(parent1, parent2)
End if
edgeCount = edgeCount + 1
End while
Главный цикл будет выполняться до тех пор, пока значение переменной edgeCount не совпадет с числом ребер в графе или пока значение переменной includedCount не покажет, что мы добавили достаточно ребер, чтобы образовать остовное дерево. Заметьте, что остовное дерево в графе с N вершинами должно иметь N – 1 ребро.
Внутри цикла мы в первую очередь находим родителей вершин, соединяемых очередным добавляемым ребром. Если эти вершины принадлежат разбиениям с различными корнями, то добавление ребра между ними не приведет к появлению цикла, а два разбиения сольются в одно с общим корнем. Сложность этого алгоритма совпадает со сложностью используемого алгоритма сортировки, поскольку число операций в цикле while линейно по числу ребер. Поэтому сложность алгоритма Крускала поиска МОД равна O(E log E).
