Алгоритм Прима

Пометим узлы, соединенные дугами в остовном дереве, постоянными метками, а еще не соединенные узлы — временными метками.

Шаг 0. Выберем произвольный узел, назовем его V ₁и пометим его постоянным значением ноль (т.е. Р ₁=0). Пометим все остальные узлы временно значениями T_j, равными d _{1 j} для V_j.

Шаг 1. Среди всех временных меток выберем одну (например, T_j) с наименьшим значением и сделаем ее постоянной. Включим дугу со значением d_ij = T_ij в минимальное остовное дерево, в котором V_i — постоянный узел и T_j = d_ij.

Шаг 2. Пусть V_j — последний узел, только что ставший постоянным. Для каждого временного узла V_k пусть T_k ← mim{ T_k, d_jk }. Если нет временных меток, то конец, иначе вернуться на шаг 1.

Анализ алгоритма Прима. На шаге 1 производится (n - 1) + (n - 2) + … + 1 =О(n²) сравнений. На шаге 2 осуществляется (n - 2) + … + 1 = О (n ²) сравнений. Таким образом, этот алгоритм снова является алгоритмом трудоемкости О (n ²). •

Замечание. Алгоритм Прима можно использовать и для максимальных остовных деревьев, просто заменяя минимум на максимум (здесь d_ij = -∞, если нет дуги).

Пример 3.1. Проиллюстрируем алгоритм Прима для сети со значениями величин d_ij, указанными в таблице 7.

Если данные сети представлены в матричной форме, алгоритм Прима можно описать следующим образом:

Табл. 7. Матрица расстояний d_ij, пример 3

узел
		∞		∞		∞
	∞		∞		∞
		∞				∞
	∞
		∞				∞
	∞		∞		∞

Шаг 0. Вычеркнуть все элементы в первом столбце и пометить первую строку.

Шаг 1. Выбрать минимальный элемент среди всех элементов в помеченных строках, пусть, например, минимальный элемент есть d_ij (вычеркнутые элементы выбирать нельзя). Если все элементы в помеченных строках вычеркнуты, то конец.

Шаг 2. Вычеркнуть j -й столбец и пометить i-ю строку. Вернуться на шаг 1.

Если применить алгоритм Прима к таблице 7, то после выбора двух элементов вычисления будут выглядеть так, как показано в таблице 8 (выбранные элементы заключены в рамку).

Табл. 8.

узел
		∞		∞		∞
	∞		∞		∞
		∞				∞
	∞
		∞				∞
	∞		∞		∞
Порядок постоянных меток	0	4	1	3	2	5

Дуги в порядке получения: e ₁₃ – e ₃₅ – e ₃₄ – e ₄₂ – e₄₆.