/p>
o Щоб знайденого ребра, вершину приналежну безлічі залишилися:
В· Викреслюємо з безлічі залишилися.
В· Додаємо до безлічі остовних.
вибрати початковий вузол
сформувати початкову облямівку, що складається з вершин,
сусідніх з початковим узломв графі є вершини, що не потрапили в дерево do
вибрати ребро з дерева в облямівку з найменшою вагою
додати кінець ребра до дерева
змінити облямівку, для чого
Додати в облямівку вершини, сусідні з новою
оновити список ребер з дерева в облямівку так,
щоб він складався з ребер найменшої ваги
end while
2.2 Псевдокод алгоритму
MST_PRIM (G, w, r)
for (Для) кожної вершини u є V [G]
2 do key [u] " - INFINITY
prev [u] " - NIL
key [r] " - 0
Q "- V [G]
while Q не порожня
do u "- Extract_Min (Q)
8 for (Для) кожній вершини v є Adj [u]
9 do if v є Q і w (u, v) < key [v]
10 then prev [v] " - u
key [v] " - w (u, v)
2.3 Блок-схема алгоритму
В
В
В
2.4 Код програми
В
2.5 Оцінка складності
Час роботи алгоритму Прима залежить від обраної реалізації черги з пріоритетами Q. Якщо реалізувати її як бінарну піраміду, то для виконання ініціалізації в рядках 1-5 потрібно часу О (V). Тіло циклу while виконується | V | раз, а оскільки кожна операція Extract_Min займає час О (lg V), загальний час всіх викликів процедур Extract__Min становить О (V * lg V). Цикл for у рядках 8-11 виконується всього О (Е) раз, оскільки сума довжин всіх списків суміжності дорівнює 2 | Е |. Всередині циклу for перевірка на приналежність Q в рядку 9 може ...
