Знаходження дерева мінімальної довжини використовуючи алгоритм Прима

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

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

Оскільки граф з вершинами містить різних кістякових дерев, то рішення цієї задачі «сліпим» перебором варіантів вимагало б надзвичайно великих обчислень навіть при відносно малих . Однак для її рішення існують більш ефективні алгоритми, серед яких найвідомішими є описаний нижче алгоритм Прима, алгоритм Крускала та алгоритм Борувки.

Отже, алгоритм Прима відноситься до так званих «жадібних» алгоритмів. Жадібні алгоритми діють, використовуючи, в кожен момент, лише частину результатних даних і беручи краще рішення на основі цієї частини. У нашому випадку, на кожному кроці розглядається множина ребер графа, що допускають приєднання до вже побудованої частини кістякового дерева, і вибирається серед них ребро з найменшою довжиною. Повторюючи цю процедуру, отримують кістякове дерево найменшої довжини.

дерево найменшої довжини, алгоритм Прима

Ілюстрація роботи алгоритму Прима

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

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

Знаходження мінімального кістякового дерева використовуючи алгоритм Прима — приклад:

Знайти дерево мінімальної вартості для неорієнтованого графа зображеного на рисунку нижче, використовуючи для цьому алгоритм Прима.

Алгоритм Прима приклад

Неорієнтований граф задачі

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

Отже, вершина «1» з'єднана з вершинами «2», «3» і «4». Вибираємо серед них ту, яка має з початковою вершиною спільне ребро найменшої довжини. В нашому випадку такою є вершина номер три (довжина ребра рівна одиниці). Цю вершину, разом з ребром  додаємо в шукане дерево.

На наступному кроці, визначаємо вершину, яка має спільне ребро найменшої довжини з вершинами «1» або «3». Очевидно, що це буде вершина «6» (поєднана з вершиною «3» ребром , довжина якого становить 4).

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

Повторюючи аналогічні дії далі, доповнюємо дерево вершинами «2», «4» та ребрами відповідно і на цьому робота алгоритму Прима завершується.

Алгоритм Прима приклад

Дерево найкоротших шляхів

У підсумку, отримуємо кістяк в якому сума довжин ребер мінімальна.

Блок-схема алгоритму Прима

Алгоритм Прима блок-схема

Матеріал був корисним, поділись в соціальних мережах:
Якщо тобі сподобалась дана тема, залиш свій коментар