Реализация алгоритма Прима
Обсудим реализацию рассмотренных алгоритмов и попробуем получить хорошие оценки времени выполнения. Как вы увидите, алгоритмы Прима и Крускала с правильным выбором структур данных могут быть реализованы с временем выполнения O(m log n).
Хотя для алгоритма Прима доказательство правильности сильно отличалось от доказательства алгоритма Дейкстры для кратчайшего пути, реализации алгоритмов Прима и Дейкстры почти идентичны.
По аналогии с алгоритмом Дейкстры для принятия решения о том, какой узел v добавить следующим в растущее множество S, следует хранить стоимости присоединения a(v) = mine=(u, v):uѮS ce для каждого узла v Ѯ V − S.
Как и в предыдущем случае, узлы хранятся в приоритетной очереди, использующей стоимости присоединения a(v) в качестве ключей; узел выбирается операцией ExtractMin, а для обновления стоимости присоединения используются операции ChangeKey.
Всего существует n − 1 итераций, на которых выполняется операция ExtractMin, а операция ChangeKey выполняется не более одного раза для каждого ребра. Следовательно:
При использовании приоритетной очереди алгоритм Прима для графа с n узлами и m ребрами может быть реализован с выполнением за время O(m) с добавлением времени n операций ExtractMin и m операций ChangeKey.
Как и в случае с алгоритмом Дейкстры, приоритетная очередь на базе кучи позволяет реализовать операции ExtractMin и ChangeKey за время O(log n), а следовательно, обеспечивает общее время выполнения O(m log n).
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу