Изменения

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

Алгоритм Прима

6 байт добавлено, 17:32, 13 октября 2014
Реализация
Ребра дерева восстанавливаются из его неявного вида после выполнения алгоритма.<br>
Чтобы упростить операцию <tex>\textmathrm{decreaseKey}</tex> можно написать кучу на основе [[АВЛ-дерево | сбалансированного бинарного дерева поиска]]. Тогда просто удалим вершину и добавим ее обратно уже с новым ключом. Асимптотика таких преобразований <tex>O(\log n)</tex>. Если же делать с [[Двоичная_куча | бинарной кучей]], то вместо операции <tex>\textmathrm{decreaseKey}</tex>, будем всегда просто добавлять вершину с новым ключом, если из кучи достали вершину с ключом, значение которого больше чем у нее уже стоит, просто игнорировать. Вершин в куче будет не больше <tex>n^2</tex>, следовательно, операция <tex>\textmathrm{extractMin}</tex> будет выполняться за <tex>O(\log n^2)</tex>, что равно <tex>O(\log n)</tex>. Максимальное количество вершин, которое мы сможем достать, равняется количеству ребер, то есть <tex>m</tex>, поэтому общая асимптотика составит <tex>O(m \log n)</tex>, что хорошо только на разреженных графах.
==Пример==
Анонимный участник

Навигация