Алгоритм Р. Прима (1957 г.)

Алгоритм Р. Прима (1957 г.) похож на алгоритм Краскала; основное различие состоит в том, что в этом алгоритме строится разрастающееся дерево, более точно: последовательность деревьев S1 Ì S2 Ì… Ì Sn; где дерево Si = <Vi;Ei> содержит i вершин (i = 1;… ; n).

1. Пусть V1 = , где x1 Î V - произвольная вершина G, E1 = . Следующий шаг выполнять для i = 2… ;n.

2. Получить дерево Si из дерева Si-1 добавлением ребра графа G наименьшего веса (среди тех рeбер, при добавлении которых к Si-1 вновь образуется дерево). Исключить из G данное ребро.