Теория и практика параллельных вычислений
Последовательный алгоритм Прима
Алгоритм начинает работу с произвольной вершины графа, выбираемой в качестве корня дерева, и в ходе последовательно выполняемых итераций расширяет конструируемое дерево до МОД. Пусть VT есть множество вершин, уже включенных алгоритмом в МОД, а величины di, 1in, характеризуют дуги минимальной длины от вершин, еще не включенных в дерево, до множества VT, т.е.
(если для какой-либо вершины iVT не существует ни одной дуги в VT, значение di устанавливается равным ?). В начале работы алгоритма выбирается корневая вершина МОД s и полагается VT={s}, ds=0.
Действия, выполняемые на каждой итерации алгоритма Прима, состоят в следующем:
- определяются значения величин di для всех вершин, еще не включенных в состав МОД;
- выбирается вершина t графа G, имеющая дугу минимального веса до множества VTt:dt, iVT;
- вершина t включается в VT.
После выполнения n-1 итерации метода МОД будет сформировано. Вес этого дерева может быть получен при помощи выражения
Трудоемкость нахождения МОД характеризуется квадратичной зависимостью от числа вершин графа T1~n2.
