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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Задача о максимальном ребре минимального веса)
м (Источники информации: категория)
(не показано 39 промежуточных версий 3 участников)
Строка 2: Строка 2:
  
 
==Идея==
 
==Идея==
Будем последовательно строить подграф <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>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>.
 +
Для проверки возможности добавления ребра используется  [[СНМ (реализация с помощью леса корневых деревьев) | система непересекающихся множеств]].
  
 
==Реализация==
 
==Реализация==
 
  <font color=green>// <tex>G</tex> {{---}} исходный граф</font>
 
  <font color=green>// <tex>G</tex> {{---}} исходный граф</font>
 
  <font color=green>// <tex>F</tex> {{---}} минимальный остов</font>
 
  <font color=green>// <tex>F</tex> {{---}} минимальный остов</font>
<font color=green>// для проверки возможности добавления ребра используется система непересекающихся множеств</font>
 
 
  '''function''' <tex>\mathtt{kruskalFindMST}():</tex>
 
  '''function''' <tex>\mathtt{kruskalFindMST}():</tex>
 
     <tex> \mathtt{F} \leftarrow V(G)</tex>
 
     <tex> \mathtt{F} \leftarrow V(G)</tex>
Строка 13: Строка 13:
 
     '''for''' <tex>vu \in E(G)</tex>
 
     '''for''' <tex>vu \in E(G)</tex>
 
       '''if''' <tex>v</tex> и <tex>u</tex> в разных компонентах связности <tex>F</tex>
 
       '''if''' <tex>v</tex> и <tex>u</tex> в разных компонентах связности <tex>F</tex>
           <tex> \mathtt{F}\ =\ \mathtt{F} \bigcup \mathtt{vu}\</tex>
+
           <tex> \mathtt{F}\ =\ \mathtt{F} \bigcup vu\</tex>
 +
    '''return''' <tex> \mathtt{F} </tex>
  
 
==Задача о максимальном ребре минимального веса==
 
==Задача о максимальном ребре минимального веса==
Очевидно, что максимальное ребро в MST минимально. Пусть это не так, тогда рассмотрим разрез, который оно пересекает. В этом разрезе должно быть ребро с меньшим весом, иначе максимальное ребро было бы минимальным, но в таком случае минимальный остов не является минимальным, следовательно, максимальное ребро в минимальном остовном дереве минимально. Если же максимальное ребро в остовном дереве минимально, то такое дерево может не быть минимальным. Зато его можно найти быстрее чем MST, а конкретно за <tex>O(E)</tex>. Описанный далее алгоритм ищет максимальное ребро минимального веса, точнее ребро максимального веса минимального остовного дерева. С помощью [[Поиск_k-ой_порядковой_статистики_за_линейное_время | алгоритма поиска k-ой порядковой статистики]] найдем ребро-медиану за <tex>O(E)</tex> и разделим множество ребер на два равных по мощности так, чтобы в первом подмножестве все ребра не превосходили ребро-медиану, а во втором были не меньше его. Запустим [[Использование_обхода_в_глубину_для_проверки_связности|обход в глубину]], чтобы проверить образуют ли ребра из первого подмножества остов, содержащий все вершины графа. Если да, то самые легкие и все безопасные ребра находятся в первом подмножестве, поэтому рекурсивно запустим алгоритм от него, а второе подмножество ребер "выкинем". В противном случае часть безопасных ребер, включая ребро, которое мы ищем, находится во втором подмножестве, поэтому сконденсируем в супервершины получившиеся несвязные компоненты и рассмотрим граф с этими вершинами и ребрами из второго подмножества. В сконденсированных компонентах могут быть небезопасные ребра, но это не имеет значения, так как вес всех ребер первого подмножества меньше веса ребра, которого мы ищем, следовательно, они не повлияют на ответ. На последнем шаге останутся всего две компоненты связности, а в первом подмножестве будет содержаться лишь одно ребро, это ребро и будет максимальным ребром минимального веса или максимальным ребром минимального остова, так как оно наименьшее по весу среди всех ребер, пересекающих <tex> \langle S, T \rangle </tex> разрез между данными компонентами. На каждом шаге ребер становится в два раза меньше, а все операции выполняются за время пропорциональное количеству ребер на текущем шаге, следовательно, время работы алгоритма <tex>O(E+\frac{E}{2}+\frac{E}{4}+...+1)=O(E)</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
Строка 62: Строка 66:
 
==Асимптотика==
 
==Асимптотика==
 
Сортировка <tex>E</tex> займет <tex>O(E\log E)</tex>.<br>
 
Сортировка <tex>E</tex> займет <tex>O(E\log E)</tex>.<br>
Работа с [[СНМ (реализация с помощью леса корневых деревьев) | системой непересекающихся множеств]] займет <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)</tex>.
 
Алгоритм работает за <tex>O(E(\log E+\alpha(V))) = O(E\log E)</tex>.
  
Строка 77: Строка 81:
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Остовные деревья ]]
+
[[Категория: Остовные деревья]]
 +
[[Категория: Построение остовных деревьев]]

Версия 20:59, 7 сентября 2015

Алгоритм Краскала (англ. 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].

См. также

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