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

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

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

Див. також

• Алгоритм Крускала

Посилання

• Рыбаков Г. (2005). «Минимальные остовные деревья». САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ; ФАКУЛЬТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ И ПРОГРАММИРОВАНИЯ; КАФЕДРА КОМПЬЮТЕРНЫХ ТЕХНОЛОГИЙ; ДИСКРЕТНАЯ МАТЕМАТИКА: АЛГОРИТМЫ. http://rain.ifmo.ru/cat/view.php/theory/graph-spanning-trees/mst-2005. 
• Алгоритм Прима (Java Applet)