322
правки
Изменения
Новая страница: «Алгоритм Краскала - алгоритм поиска минимального остовного дерева (остова) во взвешенном …»
Алгоритм Краскала - алгоритм поиска минимального остовного дерева (остова) во взвешенном ориентированном связном графе.
==Идея==
Обозначим за <tex>T</tex> минимальный остов графа <tex>G</tex>. Будем последовательно строить подграф <tex>F</tex> графа <tex>G</tex> ("растущий лес"), поддерживая инвариант <tex>F \subset T</tex>. Начнем с того, что включим в <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 \subset T</tex>, и можно добавить это ребро в <tex>F</tex>.<br>
После обхода всех ребер в <tex>F</tex> включены те и только те ребра, которые продолжают его до <tex>T</tex>, значит, <tex>F=T</tex>.
==Реализация==
<b>Вход</b>: граф <tex>G = (V, E)</tex><br>
<b>Выход</b>: минимальный остов <tex>F</tex> графа <tex>G</tex><br>
1) <tex>F := (V, \varnothing)</tex><br>
1) Отсортируем <tex>E</tex> по весу ребер.<br>
2) Заведем систему непересекающихся множеств (DSU) и инициализируем ее множеством <tex>V</tex>.<br>
3) Перебирая ребра <tex>uv \in EG</tex> в порядке увеличения веса, смотрим, одинакового ли представителя для <tex>u</tex> и <tex>v</tex> возвращает DSU. Если нет, то делаем слияние этих представителей в DSU и полагаем <tex>F := F + uv</tex>.<br>
==Асимптотика==
Сортировка <tex>E</tex> займет <tex>O(ElogE)</tex>.<br>
Работа с DSU займет <tex>O(E\alpha(V))</tex>, где <tex>\alpha(V)</tex> - обратная функция Аккермана, которая не превосходит 5 во всех практических приложениях и которую можно принять за константу.<br>
Алгоритм работает за <tex>O(E(logE+\alpha(V))) = O(ElogE) = O(ElogV^2) = O(ElogV)</tex>.
==Идея==
Обозначим за <tex>T</tex> минимальный остов графа <tex>G</tex>. Будем последовательно строить подграф <tex>F</tex> графа <tex>G</tex> ("растущий лес"), поддерживая инвариант <tex>F \subset T</tex>. Начнем с того, что включим в <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 \subset T</tex>, и можно добавить это ребро в <tex>F</tex>.<br>
После обхода всех ребер в <tex>F</tex> включены те и только те ребра, которые продолжают его до <tex>T</tex>, значит, <tex>F=T</tex>.
==Реализация==
<b>Вход</b>: граф <tex>G = (V, E)</tex><br>
<b>Выход</b>: минимальный остов <tex>F</tex> графа <tex>G</tex><br>
1) <tex>F := (V, \varnothing)</tex><br>
1) Отсортируем <tex>E</tex> по весу ребер.<br>
2) Заведем систему непересекающихся множеств (DSU) и инициализируем ее множеством <tex>V</tex>.<br>
3) Перебирая ребра <tex>uv \in EG</tex> в порядке увеличения веса, смотрим, одинакового ли представителя для <tex>u</tex> и <tex>v</tex> возвращает DSU. Если нет, то делаем слияние этих представителей в DSU и полагаем <tex>F := F + uv</tex>.<br>
==Асимптотика==
Сортировка <tex>E</tex> займет <tex>O(ElogE)</tex>.<br>
Работа с DSU займет <tex>O(E\alpha(V))</tex>, где <tex>\alpha(V)</tex> - обратная функция Аккермана, которая не превосходит 5 во всех практических приложениях и которую можно принять за константу.<br>
Алгоритм работает за <tex>O(E(logE+\alpha(V))) = O(ElogE) = O(ElogV^2) = O(ElogV)</tex>.
