функція. Отпимального каркас ще називають найкоротшою зв'язує мережею. Завдання про відшукання оптимального каркаса є однією з найбільш часто виникаючих завдань в теорії графів. p align="justify"> Існує велика кількість алгоритмів пошуку оптимального каркаса, що показує різні результати для різних типів графів. Очевидним є метод знаходження всіх каркасів і виділення з них каркаса з мінімальною функцією вартості. Однак такий підхід вимагає значних обчислювальних ресурсів для великих графів. До найбільш вживаним алгоритмам пошуку оптимального каркаса відносяться алгоритм Краскала, алгоритм Прима, алгоритм Солліне, алгоритм Тар'я-Черітон. Ці алгоритми гарантовано знаходять оптимальний каркас, при цьому їх ефективність різна для різних типів графів. p align="justify"> У цій роботі розглядається реалізація алгоритму Прима пошуку оптимального каркаса. Алгоритм Прима має перевагу перед іншими алгоритмами знаходження оптимального каркаса в графах, близьких до повним. br/>
. Алгоритм Прима знаходження оптимального каркаса
Алгоритм Прима породжує оптимальний каркас допомогою розростання одного поддерева Ts.
Розростання поддерева Ts відбувається за рахунок приєднання ребер
(vi, vj)
де vi? Ts і vj ~? Ts, причому додається ребро повинно мати найменшу вагу cij. Процес продовжується до тих пір, поки число ребер в Ts стане рівним n-1. p align="justify"> Алгоритм починає роботу з присвоєння кожній вершині vj ~? Ts позначки [aj, bj], де aj на кожному кроці є ближня до vj вершина з поддерева Ts, а bj вага ребра (aj, bj). На кожному кроці виконання алгоритму вершина, наприклад v * j, з найменшою позначкою bj приєднується до ts допомогою додавання ребра (a * j, v * j). Оскільки до Ts додана нова вершина v * j, то, може бути, доведеться змінити позначки [aj, bj] у деяких вершин vj ~? Ts і після цього продовжити процес. p align="justify"> Наведемо словесний опис алгоритму
1. Нехай
Ts = {vs}
де vs - довільно вибрана вершина, і Ss = Гё.
2. Для кожної вершини vj ~? Ts знайти вершину aj? Ts таку, що
c (aj, vj) = min [c (vi, vj)] = bj
і приписати вершині vj позначку [aj, bj]. Якщо такої вершини a немає, приписати вершині vj позначку [0,?]. p align="justify">. Вибрати таку вершину v * j, що
b * j = min [bj]
Оновити дані: Ts = Ts Г€ {v * j}, Ss = Ss Г€ {(a * j, v * j)}. Якщо | T | = n, то стоп. Ребра в Ss утворюють оптимальний каркас. Якщо | Ts |
