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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 3: Строка 3:
 
==Идея==
 
==Идея==
 
Будем последовательно строить подграф <tex>F</tex> графа <tex>G</tex> ("растущий лес"), поддерживая инвариант: на каждом шаге F можно достроить до некоторого 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>F+e</tex> можно продолжить до MST, поэтому добавим это ребро в <tex>F</tex>.<br>
 
Будем последовательно строить подграф <tex>F</tex> графа <tex>G</tex> ("растущий лес"), поддерживая инвариант: на каждом шаге F можно достроить до некоторого 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>F+e</tex> можно продолжить до MST, поэтому добавим это ребро в <tex>F</tex>.<br>
Из связности G следует, что после  конце алгоритма <tex>F</tex> будет связным, а способ построения F не допускает возможности возникнуть циклам. Это означает, что получилось остовное дерево. После последнего шага алгоритма <tex>\exists</tex> MST <tex>T: F \subset T</tex>, но в <tex>F</tex> уже нельзя добавлять ребра, значит, <tex>F=T</tex>.
+
Из связности G следует, что в конце алгоритма <tex>F</tex> будет связным, а способ построения F не допускает возможности возникнуть циклам. Это означает, что получилось остовное дерево. После последнего шага алгоритма <tex>\exists</tex> MST <tex>T: F \subset T</tex>, но в <tex>F</tex> уже нельзя добавлять ребра, значит, <tex>F=T</tex>.
  
 
==Реализация==
 
==Реализация==

Версия 02:18, 2 декабря 2010

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

Идея

Будем последовательно строить подграф [math]F[/math] графа [math]G[/math] ("растущий лес"), поддерживая инвариант: на каждом шаге F можно достроить до некоторого MST. Начнем с того, что включим в [math]F[/math] все вершины графа [math]G[/math]. Теперь будем обходить множество [math]EG[/math] в порядке увеличения веса ребер. Добавление очередного ребра [math]e[/math] в [math]F[/math] может привести к возникновению цикла в одной из компонент связности [math]F[/math]. В этом случае, очевидно, [math]e[/math] не может быть включено в [math]F[/math]. В противном случае [math]e[/math] соединяет разные компоненты связности [math]F[/math] и из леммы о безопасном ребре следует, что [math]F+e[/math] можно продолжить до MST, поэтому добавим это ребро в [math]F[/math].
Из связности G следует, что в конце алгоритма [math]F[/math] будет связным, а способ построения F не допускает возможности возникнуть циклам. Это означает, что получилось остовное дерево. После последнего шага алгоритма [math]\exists[/math] MST [math]T: F \subset T[/math], но в [math]F[/math] уже нельзя добавлять ребра, значит, [math]F=T[/math].

Реализация

Вход: граф [math]G = (V, E)[/math]
Выход: минимальный остов [math]F[/math] графа [math]G[/math]
1) [math]F := (V, \varnothing)[/math]
1) Отсортируем [math]E[/math] по весу ребер.
2) Заведем систему непересекающихся множеств (DSU) и инициализируем ее множеством [math]V[/math].
3) Перебирая ребра [math]uv \in EG[/math] в порядке увеличения веса, смотрим, одинакового ли представителя для [math]u[/math] и [math]v[/math] возвращает DSU. Если нет, то делаем слияние этих представителей в DSU и полагаем [math]F := F + uv[/math].

Асимптотика

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

См. также