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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Задача о максимальном ребре минимального веса)
Строка 16: Строка 16:
  
 
==Задача о максимальном ребре минимального веса==
 
==Задача о максимальном ребре минимального веса==
Очевидно, что максимальное ребро в 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>.
+
Очевидно, что максимальное ребро в 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>.
  
 
==Пример==
 
==Пример==

Версия 13:21, 14 декабря 2014

Алгоритм Краскала (англ. 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]F[/math]. В этом случае, очевидно, [math]e[/math] не может быть включено в [math]F[/math]. В противном случае [math]e[/math] соединяет разные компоненты связности [math]F[/math], тогда существует разрез [math] \langle S, T \rangle [/math] такой, что одна из компонент связности составляет одну его часть, а оставшаяся часть графа — вторую. Тогда [math]e[/math] и есть минимальное ребро, пересекающее этот разрез. Значит, из леммы о безопасном ребре следует, что [math]F+e[/math] можно продолжить до MST, поэтому добавим это ребро в [math]F[/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 \mathtt{vu}\[/math]

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

Очевидно, что максимальное ребро в MST минимально. Пусть это не так, тогда рассмотрим разрез, который оно пересекает. В этом разрезе должно быть ребро с меньшим весом, иначе максимальное ребро было бы минимальным, но в таком случае минимальный остов не является минимальным, следовательно, максимальное ребро в минимальном остовном дереве минимально. Если же максимальное ребро в остовном дереве минимально, то такое дерево может не быть минимальным. Зато его можно найти быстрее чем MST, а конкретно за [math]O(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] — обратная функция Аккермана, которая не превосходит 4 во всех практических приложениях и которую можно принять за константу.
Алгоритм работает за [math]O(E(\log E+\alpha(V))) = O(E\log E)[/math].

См. также

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