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

 

 

Формулировка задачи. Дан взвешенный граф, в котором веса присвоены ребрам. Необходимо найти минимальное остовное дерево имеющую своим корнем одну из вершин графа.

 

Идея алгоритма. Пусть часть остовного дерева уже построена. Это утверждения всегда верно, так как в начале процесса вершина с которой начинается построение уже входит в дерево. Итак если часть основного дерева уже есть, то множество вершин графа можно разделить на два подмножества: подмножество состоящее из вершин уже построенного остовного дерева и оставшихся вершин графа.

Очевидно, что среди ребер соединяющихся эти два множества существует ребро наименьшего веса. Можно доказать, (но мы здесь этого делать не будем) что минимальное дерево проходит через это ребро.

 

Алгоритм.

 

§        Множество остовных вершин – исходная веришны

§        Множество оставшихся  - все вершины за исключением исходной.

§        Пока множество оставшихся не пусто

o       Ищем ребро соединяющее множество остовных и множество оставшихся и имеющее наименьший вес.

o       Для найденного ребра, вершину принадлежащую множеству оставшихся:

§        Вычеркиваем из множества оставшихся.

§        Добавляем к множеству остовных.