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

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

Алгоритми пошуку графами та деревами
Переліки
Пов'язані теми

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

Алгоритм
  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)
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.