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

2014-12-15T10:33:43Z

217.66.159.31: /* Задача о максимальном ребре минимального веса */

Алгоритм Краскала (англ. ''Kruskal's algorithm'') — алгоритм поиска [[Лемма о безопасном ребре#Необходимые определения | минимального остовного дерева]] (англ. ''minimum spanning tree'', ''MST'') во взвешенном [[Основные определения теории графов#Неориентированные графы | неориентированном связном графе]].

==Идея==
Будем последовательно строить подграф <tex>F</tex> графа <tex>G</tex> ("растущий лес"), пытаясь на каждом шаге достроить <tex>F</tex> до некоторого MST. Начнем с того, что включим в <tex>F</tex> все вершины графа <tex>G</tex>. Теперь будем обходить множество <tex>E(G)</tex> в порядке неубывания веса ребер. Если очередное ребро <tex>e</tex> соединяет вершины одной компоненты связности <tex>F</tex>, то добавление его в остов приведет к возникновению цикла в этой компоненте связности. В таком случае, очевидно, <tex>e</tex> не может быть включено в <tex>F</tex>. Иначе <tex>e</tex> соединяет разные компоненты связности <tex>F</tex>, тогда существует <tex> \langle S, T \rangle </tex> [[Лемма о безопасном ребре#Необходимые определения|разрез]] такой, что одна из компонент связности составляет одну его часть, а оставшаяся часть графа — вторую. Тогда <tex>e</tex> — минимальное ребро, пересекающее этот разрез. Значит, из [[Лемма о безопасном ребре#Лемма о безопасном ребре|леммы о безопасном ребре]] следует, что <tex>e</tex> является безопасным, поэтому добавим это ребро в <tex>F</tex>. На последнем шаге ребро соединит две оставшиеся компоненты связности, полученный подграф будет минимальным остовным деревом графа <tex>G</tex>.

==Реализация==
// <tex>G</tex> {{---}} исходный граф
// <tex>F</tex> {{---}} минимальный остов
// для проверки возможности добавления ребра используется система непересекающихся множеств
'''function''' <tex>\mathtt{kruskalFindMST}():</tex>
<tex> \mathtt{F} \leftarrow V(G)</tex>
<tex>\mathtt{sort}(E(G))\</tex>
'''for''' <tex>vu \in E(G)</tex>
'''if''' <tex>v</tex> и <tex>u</tex> в разных компонентах связности <tex>F</tex>
<tex> \mathtt{F}\ =\ \mathtt{F} \bigcup \mathtt{vu}\</tex>

==Задача о максимальном ребре минимального веса==
Очевидно, что максимальное ребро в MST минимально. Пусть это не так, тогда рассмотрим разрез, который оно пересекает. В этом разрезе должно быть ребро с меньшим весом, иначе максимальное ребро было бы минимальным, но в таком случае минимальный остов не является минимальным, следовательно, максимальное ребро в минимальном остовном дереве минимально. Если же максимальное ребро в остовном дереве минимально, то такое дерево может не быть минимальным. Зато его можно найти быстрее чем MST, а конкретно за <tex>O(E)</tex>. С помощью [[Поиск_k-ой_порядковой_статистики_за_линейное_время | алгоритма поиска k-ой порядковой статистики]] найдем ребро-медиану за <tex>O(E)</tex> и разделим множество ребер на два равных по мощности так, чтобы в первом подмножестве все ребра не превосходили ребро-медиану, а во втором были не меньше его. Запустим [[Использование_обхода_в_глубину_для_проверки_связности|обход в глубину]], чтобы проверить образуют ли ребра из первого подмножества остов, содержащий все вершины графа. Если да, то, так как все ребра в первом подмножестве меньше чем во втором, рекурсивно запустим алгоритм от него. В противном случае сконденсируем в супервершины получившиеся несвязные компоненты и рассмотрим граф с этими супервершинами и ребрами из второго подмножества. На последнем шаге останется одно ребро, оно и будет максимальным ребром минимального веса. На каждом шаге ребер становится в два раза меньше, а все операции выполняются за время пропорциональное количеству ребер на текущем шаге, следовательно, время работы алгоритма <tex>O(E+\frac{E}{2}+\frac{E}{4}+...+1)=O(E)</tex>. Чтобы восстановить остовное дерево, достаточно запустить алгоритм поиска в глубину и добавлять в остов только те ребра, которые не превосходят найденное алгоритмом ребро.

==Пример==
Задан неориентированный связный граф, требуется построить в нём минимальное остовное дерево. 
Создадим новый граф, содержащий все вершины из заданного графа, но не содержащий рёбер. 
Этот новый граф будет ответом, в него будут добавлены рёбра из заданного графа по ходу выполнения алгоритма. 
Отсортируем рёбра заданного графа по их весам и рассмотрим их в порядке возрастания.
{| class = "wikitable"
| Рёбра ''(в порядке их просмотра)'' || ae || cd || ab || be || bc || ec || ed
|-
| Веса рёбер ||<tex>1</tex> || <tex>2</tex> || <tex>3</tex> || <tex>4</tex> || <tex>5</tex> || <tex>6</tex> || <tex>7</tex>
|}

{| class = "wikitable"
! Изображение !! Описание
|-
|[[Файл:Mst_kruskal_1.png|200px]]
|style="padding-left: 1em" |Первое ребро, которое будет рассмотрено — '''ae''', так как его вес минимальный. 
Добавим его к ответу, так как его концы соединяют вершины из разных множеств ('''a''' — красное и '''e''' — зелёное). 
Объединим красное и зелёное множество в одно (красное), так как теперь они соединены ребром.
|-
|[[Файл:Mst_kruskal_2.png|200px]]
|style="padding-left: 1em" |Рассмотрим следующие ребро — '''cd'''. 
Добавим его к ответу, так как его концы соединяют вершины из разных множеств ('''c''' — синее и '''d''' — голубое). 
Объединим синее и голубое множество в одно (синее), так как теперь они соединены ребром.
|-
|[[Файл:Mst_kruskal_3.png|200px]]
|style="padding-left: 1em" |Дальше рассмотрим ребро '''ab'''. 
Добавим его к ответу, так как его концы соединяют вершины из разных множеств ('''a''' — красное и '''b''' — розовое). 
Объединим красное и розовое множество в одно (красное), так как теперь они соединены ребром.
|-
|[[Файл:Mst_kruskal_4.png|200px]]
|style="padding-left: 1em" |Рассмотрим следующие ребро — '''be'''. 
Оно соединяет вершины из одного множества, поэтому перейдём к следующему ребру '''bc''' 
Добавим его к ответу, так как его концы соединяют вершины из разных множеств ('''b''' — красное и '''c''' — синее). 
Объединим красное и синее множество в одно (красное), так как теперь они соединены ребром.
|-
|[[Файл:Mst_kruskal_5.png|200px]]
|style="padding-left: 1em" |Рёбра '''ec''' и '''ed''' соединяют вершины из одного множества, 
поэтому после их просмотра они не будут добавлены в ответ 
Всё рёбра были рассмотрены, поэтому алгоритм завершает работу. 
Полученный граф — минимальное остовное дерево
|}

==Асимптотика==
Сортировка <tex>E</tex> займет <tex>O(E\log E)</tex>. 
Работа с [[СНМ (реализация с помощью леса корневых деревьев) | системой непересекающихся множеств]] займет <tex>O(E\alpha(V))</tex>, где <tex>\alpha</tex> — обратная функция Аккермана, которая не превосходит 4 во всех практических приложениях и которую можно принять за константу. 
Алгоритм работает за <tex>O(E(\log E+\alpha(V))) = O(E\log E)</tex>.

==См. также==
* [[Алгоритм Прима]]
* [[Алгоритм Борувки]]

==Источники информации==
* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн — Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
* [http://ru.wikipedia.org/wiki/%D0%A4%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F_%D0%90%D0%BA%D0%BA%D0%B5%D1%80%D0%BC%D0%B0%D0%BD%D0%B0 Википедия — Функция Аккермана]
* [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D1%80%D1%83%D1%81%D0%BA%D0%B0%D0%BB%D0%B0 Википедия — Алгоритм Крускала]
* [http://en.wikipedia.org/wiki/Kruskal's_algorithm Wikipedia — Kruskal's algorithm]
* [http://e-maxx.ru/algo/mst_kruskal MAXimal :: algo :: Минимальное остовное дерево. Алгоритм Крускала]

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Остовные деревья ]]

Викиконспекты - Вклад участника [ru]

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