информационно-новостной портал
Главная / Статьи / Информатика / Программирование /

Обоснование корректности алгоритма Прима такое же, как и алгоритма Краскала

Сравним трудоемкость описанных алгоритмов для графа с n вершинами и m ребрами. В первом из них основные затраты времени падают на сортировку ребер по их весу; известно, что для выполнения сортировки m объектов требуется порядка mlog2m операций сравнения. Во втором алгоритме на i-м шаге среди n - i вершин, еще не включенных в дерево, нужно выбрать ту, чье подключение к дереву обойдется наиболее дешево (ребро, соединяющее новую вершину с одной из старых, должно быть наименьшего веса); для этого требуется порядка n - i - 1 операций. Суммируя по i, получим оценку трудоемкости алгоритма Прима: O() операций сравнения. Понятно, что для полных графов (где число ребер m=n(n-1)/2) алгоритм Прима менее трудоемок, чем алгоритм Краскала.

Опишем эффективную реализацию алгоритма Прима. На каждом шаге алгоритма каждой вершине xi, ещe не включенной в дерево, сопоставляется пометка - пара чисел [ai; bi], где bi - наименьший вес ребра, соединяющего xi с какой-либо вершиной, уже включенной в дерево, ai - номер соответствующей вершины. Таким образом,. Шаг алгоритма состоит в выборе bi* = min(bi) и добавлении к дереву ребра ai*xi* .
Просмотров: 1119 | Дата добавления: 08.02.2016