primeMin ([], M, par (X, Y)): - M = mark (X, Y, _).
primeMin ([H | T], mark (X, Y, M), XS): - H = mark (X1, Y1, Z1), Z1
Задачу перемаркировки виконує предикат remark.
У даному предикате відбувається порівняння міток вершин, інцідентних доданої вершині, з вагою ребра, що йде до доданої вершині.
Якщо вага ребра менше значення мітки, мітка міняється відповідно до п.4 алгоритму. Предикат визначений таким чином:
([], _, _, []).
remark ([H | HS], E, X, TH): - H = mark (X, _, _), remark (HS, E, X, TH).
remark ([H | T], E, X, [NH | TH]): - H = mark (X1, X2, W), elem (edge ​​(X1, X, W1), E), W1
Код програми мовою Пролог представлений у Додатку Б.
. Приклади роботи програм
Розглянемо роботу алгоритму на прикладі графа, представленого на малюнку 1. Зліва на малюнку представлений граф, праворуч - оптимальний каркас цього графа. br/>В
Рисунок 1 - Тестовий граф (ліворуч) і відповідний йому оптимальний каркас (праворуч)
каркас граф алгоритм прима
У мові Пролог даний граф кодується таким чином:
g2 (X): - X = graph
Цільова функція для цього графа
main: - g2 (X), primeInit (X, T, S, M), primeSearch (X, T, S, M, R), write ('Graph optimal carcas:'), writeln (R).
Результат
Graph optimal carcas: [edge (6, 1), edge (5, 4), edge (4, 3), edge (3, 7), edge (2, 7), edge ( 7, 1)]
Результат відповідає дійсному.
Для програми мовою Haskell визначимо головну функцію main:
main = do = [
(Nothing, 1, [(2,20), (6,23), (7,1)]),
(Nothing, 2, [(1,20), (3,15), (7,4)]),
(Nothing, 3, [(2,15), (7,9), (4,3)]),
(Nothing, 4, [(3,4), (7,16), (5,17)]),
(Nothing, 5, [(4,17), (7,25), (6,28)]),
(Nothing, 6, [(5,28), (7,36), (1,23)]),
(Nothing, 7, [(1,1), (6,36), (5,25), (4,16), (3,9), (2,4)] )
]
(graph, vf, kf, wf) = graphFromWEdges gs = primeOptimalCarcas graph wfts
Результат:
[(0,6), (6,1), (6,2), (2,3), (3,4), (0,5)]
Результат відповідає дійсному.
