Реализация алгоритма Прима

Обсудим реализацию рассмотренных алгоритмов и попробуем получить хорошие оценки времени выполнения. Как вы увидите, алгоритмы Прима и Крускала с правильным выбором структур данных могут быть реализованы с временем выполнения 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).