У даній статті розглядається задача побудови мінімального кістякового дерева для неорієнтованого зваженого графа. Нагадаємо, що кістяк – це таке дерево, яке є максимальним по включенню ребер підграфом, що не має циклів, і в якому сума довжин ребер мінімальна. Якщо вихідний граф зв’язний, то буде побудовано кістяк, якщо ж у вихідному графі кілька незв’язних компонент, то результатом буде кістяковий ліс.
Задача про знаходження мінімального кістякового дерева виникає при проектуванні ліній електропередач, трубопроводів, доріг і тому подібне, коли потрібно задані центри з’єднати деякою системою каналів зв’язку так, щоб будь-які два центри були пов’язані або каналом що їх з’єднює, або через інші центри і канали, і щоб загальна довжина (або, наприклад, вартість) каналів зв’язку була мінімальною. У цій ситуації задані центри можна вважати вершинами графа з вагами ребер, рівними довжинам (вартостям) каналів, що з’єднують ці центри. Тоді шукана мережу буде кістяковим деревом найменшої довжини (вартості).
Оскільки граф з 
вершинами містить 
різних кістякових дерев, то рішення цієї задачі «сліпим» перебором варіантів вимагало б надзвичайно великих обчислень навіть при відносно малих . Однак для її рішення існують більш ефективні алгоритми, серед яких найвідомішими є описаний нижче алгоритм Прима, алгоритм Крускала та алгоритм Борувки.
Отже, алгоритм Прима відноситься до так званих «жадібних» алгоритмів. Жадібні алгоритми діють, використовуючи, в кожен момент, лише частину результатних даних і беручи краще рішення на основі цієї частини. У нашому випадку, на кожному кроці розглядається множина ребер графа, що допускають приєднання до вже побудованої частини кістякового дерева, і вибирається серед них ребро з найменшою довжиною. Повторюючи цю процедуру, отримують кістякове дерево найменшої довжини.
Ілюстрація роботи алгоритму Прима
Робота алгоритму починається з довільної вершини і включення її в кістяк. Для графа, зображеного на рисунку вище, в якості початкової була обрана вершина 
. На наступному кроці, з усіх вершин, поєднаних з даною, шукається вершина, з’єднана ребром з найменшою довжиною. Це ребро разом з новою вершиною додається в дерево. Після цього, серед вершин, що не увійшли в дерево, шукається вершинуа, з’єднана з уже побудованою частиною кістякового дерева ребром з найменшою довжиною. Це ребро разом з новою вершиною додається в дерево і так далі.
Зазначимо, що ітераційний процес алгоритму Прима продовжується до тих пір, поки в кістяк не потраплять всі вершини розглядуваного графа (або, що те ж саме, 
ребро). В результаті буде побудований кістяк, який є мінімальним.
Знаходження мінімального кістякового дерева використовуючи алгоритм Прима – приклад:
Знайти дерево мінімальної вартості для неорієнтованого графа зображеного на рисунку нижче, використовуючи для цьому алгоритм Прима.
Неорієнтований граф задачі
Для початку, в якості стартової, вибираємо будь-яку вершину заданого графа. Нехай такою буде вершина номер один. Після цього, переходимо до визначення найближчого її сусіда.
Отже, вершина «1» з’єднана з вершинами «2», «3» і «4». Вибираємо серед них ту, яка має з початковою вершиною спільне ребро найменшої довжини. В нашому випадку такою є вершина номер три (довжина ребра 
рівна одиниці). Цю вершину, разом з ребром додаємо в шукане дерево.
На наступному кроці, визначаємо вершину, яка має спільне ребро найменшої довжини з вершинами «1» або «3». Очевидно, що це буде вершина «6» (поєднана з вершиною «3» ребром 
, довжина якого становить 4).
Наступною вершиною, яку ми приєднаємо до кістяка буде вершина під номуром чотири – саме вона з’єднана ребром найменшої довжини (ребро 
) з вершинами, що вже належать дереву мінімальної вартості.
Повторюючи аналогічні дії далі, доповнюємо дерево вершинами «2», «4» та ребрами 
, 
відповідно і на цьому робота алгоритму Прима завершується.
Дерево найкоротших шляхів
У підсумку, отримуємо кістяк в якому сума довжин ребер мінімальна.
Блок-схема алгоритму Прима
