Алгоритм Прима
Алгоритм Прима
Введение
Дан взвешенный неориентированный граф с вершинами и рёбрами. Требуется найти остовное дерево этого графа, которое соединяет все вершины и имеет наименьший суммарный вес (то есть сумма весов рёбер минимальна).
Алгоритм
Выбираем произвольную вершину . Создаём множество, состоящее из одной вершины , то есть . Далее выполняем итераций: