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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

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

Алгоритм[ред. | ред. код]

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

Приклад виконання[ред. | ред. код]

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

Prim Algorithm 0

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

Prim Algorithm 1

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

Prim Algorithm 2

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

Prim Algorithm 4

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

Prim Algorithm 6

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

Prim Algorithm 7

Див. також[ред. | ред. код]

Посилання[ред. | ред. код]

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