Алгоритм Краскала — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 100 промежуточных версий 5 участников)
Строка 1: Строка 1:
<b>Алгоритм Краскала</b>(англ. ''Kruskal's algorithm'') — алгоритм поиска [[Лемма о безопасном ребре#Необходимые определения | минимального остовного дерева]] (англ. ''minimum spanning tree'', ''MST'') во взвешенном [[Основные определения теории графов#Неориентированные графы | неориентированном связном графе]].
+
<b>Алгоритм Краскала</b> (англ. ''Kruskal's algorithm'') — алгоритм поиска [[Лемма о безопасном ребре#Необходимые определения | минимального остовного дерева]] (англ. ''minimum spanning tree'', ''MST'') во взвешенном [[Основные определения теории графов#Неориентированные графы | неориентированном связном графе]].
  
 
==Идея==
 
==Идея==
Будем последовательно строить подграф <tex>F</tex> графа <tex>G</tex> ("растущий лес"), поддерживая следующий инвариант: на каждом шаге <tex>F</tex> можно достроить до некоторого MST. Начнем с того, что включим в <tex>F</tex> все вершины графа <tex>G</tex>. Теперь будем обходить множество <tex>EG</tex> в порядке увеличения веса ребер. Добавление очередного ребра <tex>e</tex> в <tex>F</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>F+e</tex> можно продолжить до MST, поэтому добавим это ребро в <tex>F</tex>.<br>
+
Будем последовательно строить подграф <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>.
Несложно понять, что после выполнения такой процедуры получится остовное дерево, при этом его минимальность вытекает из леммы о безопасном ребре.
+
Для проверки возможности добавления ребра используется  [[СНМ (реализация с помощью леса корневых деревьев) | система непересекающихся множеств]].
  
 
==Реализация==
 
==Реализация==
<b>Вход</b>: граф <tex>G = (V, E)</tex><br>
+
<font color=green>// <tex>G</tex> {{---}} исходный граф</font>
<b>Выход</b>: минимальный остов <tex>F</tex> графа <tex>G</tex><br>
+
<font color=green>// <tex>F</tex> {{---}} минимальный остов</font>
1) <tex>F := (V, \varnothing)</tex><br>
+
'''function''' <tex>\mathtt{kruskalFindMST}():</tex>
1) Отсортируем <tex>E</tex> по весу ребер.<br>
+
    <tex> \mathtt{F} \leftarrow V(G)</tex>
2) Заведем систему непересекающихся множеств (DSU) и инициализируем ее множеством <tex>V</tex>.<br>
+
    <tex>\mathtt{sort}(E(G))\</tex>
3) Перебирая ребра <tex>uv \in EG</tex> в порядке увеличения веса, смотрим, принадлежат ли <tex>u</tex> и <tex>v</tex> одному множеству. Если нет, то объединяем множества, в которых лежат <tex>u</tex> и <tex>v</tex>, и добавляем ребро <tex>uv</tex> к <tex>F</tex>.<br>
+
    '''for''' <tex>vu \in E(G)</tex>
 +
      '''if''' <tex>v</tex> и <tex>u</tex> в разных компонентах связности <tex>F</tex>
 +
          <tex> \mathtt{F}\ =\ \mathtt{F} \bigcup vu\</tex>
 +
    '''return''' <tex> \mathtt{F} </tex>
 +
 
 +
==Задача о максимальном ребре минимального веса==
 +
Легко показать, что максимальное ребро в MST минимально. Обратное в общем случае неверно. Но MST из-за сортировки строится за <tex>O(E \log E)</tex>. Однако из-за того, что необходимо минимизировать только максимальное ребро, а не сумму всех рёбер, можно предъявить алгоритм, решающий задачу за линейное время.
 +
 
 +
С помощью [[Поиск_k-ой_порядковой_статистики_за_линейное_время | алгоритма поиска k-ой порядковой статистики]] найдем ребро-медиану за <tex>O(E)</tex> и разделим множество ребер на два равных по мощности так, чтобы ребра в первом не превосходили по весу ребер во втором. Проверим образуют ли ребра из первого подмножества остов графа, запустив [[Использование_обхода_в_глубину_для_проверки_связности|обход в глубину]].
 +
* Если да, то рекурсивно запустим алгоритм от него.
 +
* В противном случае сконденсируем получившиеся несвязные компоненты в супервершины и рассмотрим граф с этими вершинами и ребрами из второго подмножества.
 +
На последнем шаге останутся две компоненты связности и одно ребро в первом подмножестве — это максимальное ребро минимального веса.
 +
 
 +
На каждом шаге ребер становится в два раза меньше, а все операции выполняются за время пропорциональное количеству ребер на текущем шаге, тогда время работы алгоритма <tex>O(E+\frac{E}{2}+\frac{E}{4}+...+1)=O(E)</tex>.
  
 
==Пример==
 
==Пример==
Задан неориентированный связный граф, требуется построить в нём минимальное остовное дерево.<br/>
 
Создадим новый граф, содержащий все вершины из заданного графа, но не содержащий рёбер.<br/>
 
Этот новый граф будет ответом, в него будут добавлены рёбра из заданного графа по ходу выполнения алгоритма.<br/>
 
Отсортируем рёбра заданного графа по их весам и рассмотрим их в порядке возрастания.
 
 
{| class = "wikitable"
 
{| class = "wikitable"
 
| Рёбра ''(в порядке их просмотра)'' || ae || cd || ab || be || bc || ec || ed
 
| Рёбра ''(в порядке их просмотра)'' || ae || cd || ab || be || bc || ec || ed
Строка 35: Строка 44:
 
|style="padding-left: 1em" |Рассмотрим следующие ребро — '''cd'''.<br/>
 
|style="padding-left: 1em" |Рассмотрим следующие ребро — '''cd'''.<br/>
 
Добавим его к ответу, так как его концы соединяют вершины из разных множеств ('''c''' — синее и '''d''' — голубое).<br/>
 
Добавим его к ответу, так как его концы соединяют вершины из разных множеств ('''c''' — синее и '''d''' — голубое).<br/>
Объединим синие и голубое множество в одно (синие), так как теперь они соединены ребром.
+
Объединим синее и голубое множество в одно (синее), так как теперь они соединены ребром.
 
|-
 
|-
 
|[[Файл:Mst_kruskal_3.png|200px]]
 
|[[Файл:Mst_kruskal_3.png|200px]]
Строка 46: Строка 55:
 
Оно соединяет вершины из одного множества, поэтому перейдём к следующему ребру '''bc'''<br/>
 
Оно соединяет вершины из одного множества, поэтому перейдём к следующему ребру '''bc'''<br/>
 
Добавим его к ответу, так как его концы соединяют вершины из разных множеств ('''b''' — красное и '''c''' — синее).<br/>
 
Добавим его к ответу, так как его концы соединяют вершины из разных множеств ('''b''' — красное и '''c''' — синее).<br/>
Объединим красное и синие множество в одно (красное), так как теперь они соединены ребром.
+
Объединим красное и синее множество в одно (красное), так как теперь они соединены ребром.
 
|-
 
|-
 
|[[Файл:Mst_kruskal_5.png|200px]]
 
|[[Файл:Mst_kruskal_5.png|200px]]
 
|style="padding-left: 1em" |Рёбра '''ec''' и '''ed''' соединяют  вершины из одного множества,<br/>
 
|style="padding-left: 1em" |Рёбра '''ec''' и '''ed''' соединяют  вершины из одного множества,<br/>
поэтому после их рассмотра они не будут добавлены в ответ<br/>
+
поэтому после их просмотра они не будут добавлены в ответ<br/>
 
Всё рёбра были рассмотрены, поэтому алгоритм завершает работу.<br/>
 
Всё рёбра были рассмотрены, поэтому алгоритм завершает работу.<br/>
Полученный граф - минимальное остовное дерево
+
Полученный граф минимальное остовное дерево
 
|}
 
|}
  
 
==Асимптотика==
 
==Асимптотика==
 
Сортировка <tex>E</tex> займет <tex>O(E\log E)</tex>.<br>
 
Сортировка <tex>E</tex> займет <tex>O(E\log E)</tex>.<br>
Работа с [[СНМ (реализация с помощью леса корневых деревьев) | DSU]] займет <tex>O(E\alpha(V))</tex>, где <tex>\alpha</tex> - обратная функция Аккермана, которая не превосходит 4 во всех практических приложениях и которую можно принять за константу.<br>
+
Работа с СНМ займет <tex>O(E\alpha(V))</tex>, где <tex>\alpha</tex> обратная функция Аккермана, которая не превосходит <tex>4</tex> во всех практических приложениях и которую можно принять за константу.<br>
Алгоритм работает за <tex>O(E(\log E+\alpha(V))) = O(E\log E) = O(E\log V^2) = O(E\log V)</tex>.
+
Алгоритм работает за <tex>O(E(\log E+\alpha(V))) = O(E\log E)</tex>.
  
 
==См. также==
 
==См. также==
Строка 72: Строка 81:
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Остовные деревья ]]
+
[[Категория: Остовные деревья]]
 +
[[Категория: Построение остовных деревьев]]

Текущая версия на 19:18, 4 сентября 2022

Алгоритм Краскала (англ. Kruskal's algorithm) — алгоритм поиска минимального остовного дерева (англ. minimum spanning tree, MST) во взвешенном неориентированном связном графе.

Идея

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

Реализация

// [math]G[/math] — исходный граф
// [math]F[/math] — минимальный остов
function [math]\mathtt{kruskalFindMST}():[/math]
   [math] \mathtt{F} \leftarrow V(G)[/math]
   [math]\mathtt{sort}(E(G))\[/math]
   for [math]vu \in E(G)[/math]
      if [math]v[/math] и [math]u[/math] в разных компонентах связности [math]F[/math]
         [math] \mathtt{F}\ =\ \mathtt{F} \bigcup vu\[/math]
   return [math] \mathtt{F} [/math]

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

Легко показать, что максимальное ребро в MST минимально. Обратное в общем случае неверно. Но MST из-за сортировки строится за [math]O(E \log E)[/math]. Однако из-за того, что необходимо минимизировать только максимальное ребро, а не сумму всех рёбер, можно предъявить алгоритм, решающий задачу за линейное время.

С помощью алгоритма поиска k-ой порядковой статистики найдем ребро-медиану за [math]O(E)[/math] и разделим множество ребер на два равных по мощности так, чтобы ребра в первом не превосходили по весу ребер во втором. Проверим образуют ли ребра из первого подмножества остов графа, запустив обход в глубину.

  • Если да, то рекурсивно запустим алгоритм от него.
  • В противном случае сконденсируем получившиеся несвязные компоненты в супервершины и рассмотрим граф с этими вершинами и ребрами из второго подмножества.

На последнем шаге останутся две компоненты связности и одно ребро в первом подмножестве — это максимальное ребро минимального веса.

На каждом шаге ребер становится в два раза меньше, а все операции выполняются за время пропорциональное количеству ребер на текущем шаге, тогда время работы алгоритма [math]O(E+\frac{E}{2}+\frac{E}{4}+...+1)=O(E)[/math].

Пример

Рёбра (в порядке их просмотра) ae cd ab be bc ec ed
Веса рёбер [math]1[/math] [math]2[/math] [math]3[/math] [math]4[/math] [math]5[/math] [math]6[/math] [math]7[/math]
Изображение Описание
Mst kruskal 1.png Первое ребро, которое будет рассмотрено — ae, так как его вес минимальный.

Добавим его к ответу, так как его концы соединяют вершины из разных множеств (a — красное и e — зелёное).
Объединим красное и зелёное множество в одно (красное), так как теперь они соединены ребром.

Mst kruskal 2.png Рассмотрим следующие ребро — cd.

Добавим его к ответу, так как его концы соединяют вершины из разных множеств (c — синее и d — голубое).
Объединим синее и голубое множество в одно (синее), так как теперь они соединены ребром.

Mst kruskal 3.png Дальше рассмотрим ребро ab.

Добавим его к ответу, так как его концы соединяют вершины из разных множеств (a — красное и b — розовое).
Объединим красное и розовое множество в одно (красное), так как теперь они соединены ребром.

Mst kruskal 4.png Рассмотрим следующие ребро — be.

Оно соединяет вершины из одного множества, поэтому перейдём к следующему ребру bc
Добавим его к ответу, так как его концы соединяют вершины из разных множеств (b — красное и c — синее).
Объединим красное и синее множество в одно (красное), так как теперь они соединены ребром.

Mst kruskal 5.png Рёбра ec и ed соединяют вершины из одного множества,

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

Асимптотика

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

См. также

Источники информации