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

1. Пометить все вершины графа G невыбранными. Выбрать произвольную вершину и пометить ее выбранной.

2. Проверить, остались ли невыбранные вершины. Если да, то перейти к п.3, иначе – к п.6.

3. Найти ребро u=(x, y) c минимальным весом между выбранной вершиной х и невыбранной вершиной у.

4. Пометить вершину у как выбранную.

5. Присоединить ребро uк дереву Т. Перейти к п.2.

6. Конец алгоритма.

Пример. Дан взвешенный граф G (рис.6.3). На рисунке показан пошаговый процесс построения минимального остовного дерева по алгоритму Прима.

G 7 12

3 4 8 1 9

5 6

Т

1.

3 3

5

Т

2. 7

3 4 3 4

7 Т

3.

3 4 8 3 4

6 6

Т

4. 7

3 1

4 8 9 3 4 1

6 6

5.

12 Т

3 4 1 9 3 4 1 9

6 6

Рис. 6.3. Построение минимального остовного дерева по алгоритму

Прима.

Пунктиром обозначены ребра, не принадлежащие дереву Т. Они инцидентны невыбранным вершинам, среди которых на следующем шаге алгоритма ищется выбранная. В результате получится тот же граф, что и при работе по жадному алгоритму.

Алгоритм Прима принадлежит классу полиномиальных алгоритмов. Его асимптотическая оценка сложности F=O(m²) . Это означает, что при программной реализации алгоритма возможна обработка графов с числом ребер m до нескольких сотен.

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