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