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

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

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

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


Алгоритм

  1. Спочатку ребра сортують за зростанням ваги.
  2. Додають найменше ребро в дерево.
  3. Зі списку ребер із найменшою вагою вибирають таке нове ребро, щоб одна з його вершин належала дереву, а інша — ні.
  4. Це ребро додають у дерево і знову переходять до кроку 3.
  5. Робота закінчується, коли всі вершини будуть у дереві.


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


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). «Минимальные остовные деревья». Санкт-Петербургский государственный университет информационных технологий, механики и оптики; факультет информационных технологий и программирования; кафедра компьютерных технологий; дискретная математика: алгоритмы. Архів оригіналу за 2013-07-08. 
  • Алгоритм Прима (Java Applet)