Пометим узлы, соединенные дугами в остовном дереве, постоянными метками, а еще не соединенные узлы — временными метками.
Шаг 0. Выберем произвольный узел, назовем его V1и пометим его постоянным значением ноль (т.е. Р1=0). Пометим все остальные узлы временно значениями Tj, равными d1jдля Vj.
Шаг 1. Среди всех временных меток выберем одну (например, Tj) с наименьшим значением и сделаем ее постоянной. Включим дугу со значением dij = Tijв минимальное остовное дерево, в котором Vi— постоянный узел и Tj = dij.
Шаг 2. Пусть Vj — последний узел, только что ставший постоянным. Для каждого временного узла Vk пусть Tk ←mim{Tk, djk}. Если нет временных меток, то конец, иначе вернуться на шаг 1.
Анализ алгоритма Прима. На шаге 1 производится (n - 1) + (n - 2) + … + 1 =О(n2) сравнений. На шаге 2 осуществляется (n - 2) + … + 1 = О(n2) сравнений. Таким образом, этот алгоритм снова является алгоритмом трудоемкости О(n2). •
Замечание. Алгоритм Прима можно использовать и для максимальных остовных деревьев, просто заменяя минимум на максимум (здесь dij = -∞, если нет дуги).
Пример 3.1. Проиллюстрируем алгоритм Прима для сети со значениями величин dij, указанными в таблице 7.
Если данные сети представлены в матричной форме, алгоритм Прима можно описать следующим образом:
Табл. 7. Матрица расстояний dij, пример 3
узел
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
Шаг 0. Вычеркнуть все элементы в первом столбце и пометить первую строку.
Шаг 1. Выбрать минимальный элемент среди всех элементов в помеченных строках, пусть, например, минимальный элемент есть dij (вычеркнутые элементы выбирать нельзя). Если все элементы в помеченных строках вычеркнуты, то конец.
Шаг 2. Вычеркнуть j-й столбец и пометить i-ю строку. Вернуться на шаг 1.
Если применить алгоритм Прима к таблице 7, то после выбора двух элементов вычисления будут выглядеть так, как показано в таблице 8 (выбранные элементы заключены в рамку).
Табл. 8.
узел
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
Порядок постоянных меток
0
4
1
3
2
5
Дуги в порядке получения: e13 – e35 – e34 – e42 – e46.