Алгоритм Прима — жадібний алгоритм побудови мінімального кістякового дерева зваженого зв'язного неорієнтованого графу.
Побудова починається з дерева, що містить в собі одну (довільну) вершину. Протягом роботи алгоритму дерево розростається, поки не охопить усі вершини початкового графу. На кожному кроці алгоритму до поточного дерева приєднується найлегше з ребер, що з'єднують вершину з побудованого дерева і вершину, що не належить дереву.
Алгоритм
Ініціалізувати дерево з однією вершиною, довільно вибраною з графа. Збільшити дерево на одне ребро: із ребер, що з’єднують дерево з вершинами, які ще не в дереві, знайти ребро мінімальної ваги та додати його у дерево. Повторювати крок 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.Вибрано всі вершини, мінімальне кістякове дерево побудовано
Оцінка складності
Див. також Алгоритм Крускала
Посилання
Алгоритм Прима (Java Applet)