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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Источники информации: категория)
Строка 1: Строка 1:
 +
{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
 +
|+
 +
|-align="center"
 +
|'''НЕТ ВОЙНЕ'''
 +
|-style="font-size: 16px;"
 +
|
 +
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
 +
 +
Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
 +
 +
Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
 +
 +
Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
 +
 +
''Антивоенный комитет России''
 +
|-style="font-size: 16px;"
 +
|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
 +
|-style="font-size: 16px;"
 +
|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
 +
|}
 +
 
<b>Алгоритм Краскала</b> (англ. ''Kruskal's algorithm'') — алгоритм поиска [[Лемма о безопасном ребре#Необходимые определения | минимального остовного дерева]] (англ. ''minimum spanning tree'', ''MST'') во взвешенном [[Основные определения теории графов#Неориентированные графы | неориентированном связном графе]].
 
<b>Алгоритм Краскала</b> (англ. ''Kruskal's algorithm'') — алгоритм поиска [[Лемма о безопасном ребре#Необходимые определения | минимального остовного дерева]] (англ. ''minimum spanning tree'', ''MST'') во взвешенном [[Основные определения теории графов#Неориентированные графы | неориентированном связном графе]].
  

Версия 08:27, 1 сентября 2022

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.

Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.

Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.

Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.

Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

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

См. также

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