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

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