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

Алгоритм Прима — жадібний алгоритм побудови мінімального кістякового дерева зваженого зв'язного неорієнтованого графу.

Побудова починається з дерева, що містить в собі одну (довільну) вершину. Протягом роботи алгоритму дерево розростається, поки не охопить усі вершини початкового графу. На кожному кроці алгоритму до поточного дерева приєднується найлегше з ребер, що з'єднують вершину з побудованого дерева і вершину, що не належить дереву.

Алгоритм

1. Ініціалізувати дерево з однією вершиною, довільно вибраною з графа.
2. Збільшити дерево на одне ребро: із ребер, що з’єднують дерево з вершинами, які ще не в дереві, знайти ребро мінімальної ваги та додати його у дерево.
3. Повторювати крок 2, доки всі вершини не будуть у дереві.

Приклад виконання

1.Початковий зважений граф. Числа біля ребер показують їх вагу, яку можна розглядати як відстань між вершинами.

2. За початкову довільно обирають вершину D. Кожна з вершин A, B, E і F з'єднана з D єдиним ребром. Вершина A — найближча до D, і вибирається як друга вершина разом з ребром AD.

3.Наступна вершина — найближча до будь-якої з обраних вершин D або A. B віддалена від D на 9 і від A — на 7. Відстань до E дорівнює 15, а до F — 6. F є найближчою вершиною, тому вона включається в дерево F разом з ребром DF.

4.Аналогічними кроками приходимо до такого дерева. У цьому разі є можливість вибрати або C, або E, або G. C віддалена від B на 8, E віддалена від B на 7, а G віддалена від F на 11. E — найближча вершина, тому обирають E і ребро BE.

5.Єдина вершина, що залишилася — G. Відстань від F до неї одно 11, від E — 9. E ближче, тому обирають вершину G і ребро EG.

6.Вибрано всі вершини, мінімальне кістякове дерево побудовано

Оцінка складності

Див. також

• Алгоритм Крускала

Посилання

• Рыбаков Г. (2005). Минимальные остовные деревья. Санкт-Петербургский государственный университет информационных технологий, механики и оптики; факультет информационных технологий и программирования; кафедра компьютерных технологий; дискретная математика: алгоритмы. Архів оригіналу за 8 липня 2013. Процитовано 31 серпня 2011.