Изменения

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

Минимально узкое остовное дерево

10 байт убрано, 23:31, 8 января 2017
Асимптотика
Найдём максимальное ребро в нашем дереве. Добавим рёбра с весом меньше максимального при помощи [[СНМ (наивные реализации)|СНМ]], чтобы определить его связность. Если в результате у нас все вершины лежат в одном множестве, значит наше дерево не является <tex>\mathrm{MBST}</tex>, иначе оно <tex>\mathrm{MBST}</tex>.
=== Асимптотика ===
По каждому ребру пройдём один раз, для поиска максимального, займёт <tex>O(N)</tex>, где <tex>N -</tex> количество число рёбер в графе.<br>Работа с СНМ займет <tex>O(N\alpha(V))</tex>, где <tex>\alpha</tex> — обратная функция Аккермана, которая не превосходит <tex>4</tex> во всех практических приложениях и которую можно принять за константу.<br>В результате получаем алгоритм работающий за линейное время <tex>O(N)</tex>.
=== Псевдокод ===
45
правок

Навигация