Изменения

Перейти к: навигация, поиск

Алгоритм Краскала

715 байт убрано, 20:59, 7 сентября 2015
м
Источники информации: категория
Легко показать, что максимальное ребро в MST минимально. Обратное в общем случае неверно. Но MST из-за сортировки строится за <tex>O(E \log E)</tex>. Однако из-за того, что необходимо минимизировать только максимальное ребро, а не сумму всех рёбер, можно предъявить алгоритм, решающий задачу за линейное время.
Описанный далее алгоритм ищет максимальное ребро минимального веса и одновременно строит остовное дерево. С помощью [[Поиск_k-ой_порядковой_статистики_за_линейное_время | алгоритма поиска k-ой порядковой статистики]] найдем ребро-медиану за <tex>O(E)</tex> и разделим множество ребер на два равных по мощности подмножества так, чтобы ребра в первом ребра не превосходили медиану, а по весу ребер во втором были не меньше нее. Проверим образуют ли ребра из первого подмножества остов графа, запустив [[Использование_обхода_в_глубину_для_проверки_связности|обход в глубину]].
* Если да, то рекурсивно запустим алгоритм от него.
* В противном случае просмотрим ребра в нем, если текущее ребро соединяет разные компоненты связности (проверим с помощью СНМ за <tex>O(1)</tex>), то добавим его в остов и объединим компоненты. Сконденсируем сконденсируем получившиеся несвязные компоненты в супервершины и рассмотрим граф с этими вершинами и ребрами из второго подмножества.На последнем шаге останутся две компоненты связности и одно ребро в первом подмножестве — это максимальное ребро минимального веса, добавим его в остов. Получившийся остов может не быть минимальным, но все ребра в нем не превосходят по весу ребра, которое мы нашли.
На каждом шаге ребер становится в два раза меньше, а все операции выполняются за время пропорциональное количеству ребер на текущем шаге, тогда время работы алгоритма <tex>O(E+\frac{E}{2}+\frac{E}{4}+...+1)=O(E)</tex>.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Остовные деревья ]][[Категория: Построение остовных деревьев]]

Навигация