3.2. Алгоритм Прима [48]

Этот алгоритм порождает SST посредством разрастания только одного поддерева, например Та, содержащего больше одной вершины. «Одиночные» вершины рассматриваются как отдельные поддеревья. Поддерево постепенно разрастается за счет присоединения ребер где причем добавляемое ребро должно иметь наименьший вес Процесс продолжается до тех пор, пока число ребер в не станет равным Тогда поддерево будет требуемым SST. Впервые такая частная форма операции была предложена Примом [48], а эффективную технику ее реализации дали Дейкстра [17] и Кевин с Уитни [351.

Алгоритм начинает работу с присвоения каждой вершине пометки где на каждом шаге есть ближайшая к вершина из поддерева а ; — вес ребра каждом шаге выполнения алгоритма вершина, например с наименьшей пометкой ; присоединяется к Та посредством добавления ребра Поскольку к Та добавлена новая вершина то, может быть, придется изменить пометки некоторых вершин (если, например, с меньше существующей пометки и после этого продолжить процесс. Такая процедура расстановки пометок очень похожа на ту, которая используется в задаче о кратчайшем пути при применении алгоритма Дейкстры (гл. 8, разд. 2.1).

Алгоритм имеет следующий вид:

Шаг 1. Пусть где произвольно выбранная вершина, и является множеством ребер, входящих в

Шаг 2. Для каждой вершины найти вершину такую, что

и приписать вершине пометку Если такой вершины нет, т. е. при приписать вершине пометку

Шаг 3. Выбрать такую вершину что

Обновить данные:

Если то остановиться. Ребра в образуют SST.

Если то перейти к шагу 4.

Шаг 4. Для всех таких, что обновить пометки следующим образом.

Если то положить и вернуться к шагу 3.

Если ; с то перейти к шагу 3.