Изменения

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

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

97 байт убрано, 16:27, 17 декабря 2014
Задача о максимальном ребре минимального веса
Описанный далее алгоритм ищет максимальное ребро минимального веса и одновременно строит остовное дерево. С помощью [[Поиск_k-ой_порядковой_статистики_за_линейное_время | алгоритма поиска k-ой порядковой статистики]] найдем ребро-медиану за <tex>O(E)</tex> и разделим множество ребер на два равных по мощности подмножества так, чтобы в первом ребра не превосходили медиану, а во втором были не меньше ее. Проверим образуют ли ребра из первого подмножества остов графа, запустив [[Использование_обхода_в_глубину_для_проверки_связности|обход в глубину]].
* Если да, то рекурсивно запустим алгоритм от него.
* В противном случае просмотрим ребра в нем, если текущее ребро соединяет разные компоненты связности (проверим с помощью [[СНМ (реализация с помощью леса корневых деревьев) | СНМ]] за <tex>O(1)</tex>), то добавим его в остов. Запустим алгоритм от несвязных компонент и ребер второго подмножества.
На последнем шаге останутся две компоненты связности и одно ребро в первом подмножестве — это максимальное ребро минимального веса, добавим его в остов. Получившийся остов может не быть минимальным, но все ребра в нем не превосходят по весу ребра, которое мы нашли.
Анонимный участник

Навигация