3.2.2. Алгоритм Прима (Prim)

Определения

Алгоритм Прима характеризуется следующим:

• Строится одно дерево А;

• Построение дерева начинается с любой начальной вершины (корня дерева);

• Ребро, добавленное к А и не создающее цикла, всегда является ребром наименьшего веса, соединяющее дерево с вершиной вне дерева.

Инициализация алгоритма:

1. Выбрать любую вершину графа (корень дерева).

Выполнение алгоритма:

2. До тех пор, пока в дереве не появится n-1 ребер, выполнить:

   1. Создать очередь находящихся вне дерева и инцидентных вершине. Очередь организовать в порядке возрастания весов ребер.

   2. Выбрать из очереди ребро с наименьшим весом.

   3. Если ребро формирует цикл, то отбрасываем его, иначе добавить это в дерево.

Псевдокод

Сложность алгоритма – O(mlogn),n=|V|,m=|E|.

Пример

Инициализация:

Начальная вершина (корень дерева) – вершина а.

В дереве n-1=5-1=4 ребра

Замечания

Как и для алгоритма Краскала, в алгоритме Прима для определения циклов можно воспользоваться описателями вершин, при этом понадобятся определители двух типов – для вершин дерева (красный цвет) и для всех остальных вершин (белый цвет).

При добавлении ребра к строящемуся дереву проверяются цвета вершин:

• Если вершины разноцветные, то ребро расширяет дерево без образования цикла:

• Если обе вершины красные, то это ребро соединяет вершины дерева и создает цикл. Ребро должно быть отброшено.

Пример

3.2.3. Минимальное каркасное дерево для точек на евклидовой плоскости

Определение

Евклидовым минимальным каркасным деревом(Euclideanminimumspanningtree–EMST) является минимальное каркасное дерево множества точек на плоскости (или в более общем случае во многомерном пространстве), где веса ребер между каждой парой точек будет расстоянием между этими двумя точками.

Первый алгоритм решения задачи

1. Строится полносвязный граф, связывающий заданные nточек.

2. Рассчитываются расстояния между всеми вершинами графа по формуле

((x_i –x_j)² +(y_i – y_j)²)^1/2. Эти расстояния принимаются в качестве весов ребер графа.

3. Алгоритмом Крускала или Прима строится минимальное каркасное дерево полученного взвешенного графа.

Пример

Координаты точек (x,y):

1. (5,80);

2. (34,93);

3. (25,65);

4. (50,65);

5. (5,51);

6. (33,41);

7. (66,51);

8. (15,10);

9. (50,20);

10. (75,30);

11. (95,39);

12. (84,9).

Минимальное каркасное дерево,

общая длина 280,75

Определения

Триангуляцией¹называется планарный граф, получающийся при соединенииnвершин ребрами, такой, что нельзя добавить ни одного нового ребра без нарушения планарности (т.е. без пересечения ребрами друг друга где бы то ни было, кроме вершин).

Триангуляцию можно представить себе как планарный граф, внутренние области (области, ограниченные ребрами) которого являются треугольниками.

Одно и то же множество вершин можно триангулировать разными способами. Для решения задачи нахождения евклидового минимального каркасного дерева наилучшей является триангуляция Делоне. Доказано, что каждое ребро евклидового минимального каркасного дерева является одновременно ребром триангуляции Делоне.