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

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

АлгоритмРедагувати

  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. 
  • Алгоритм Прима (Java Applet)