, то перейти до п.4.
. Для всіх vj ~? Ts таких, що vj? Гv * j, оновити мітки наступним чином:
Якщо bj> c (v * j, vj), то покласти bj = c (v * j, vj), aj = v * j
Якщо bj <= c (v * j, vj), то не зраджувати мітку перейти до кроку 3
. Реалізація алгоритму мовою Пролог
З опису алгоритму можна виділити наступні функції:
1. Первинне размечіваніе графа, тобто Зіставлення кожній вершині мітки [aj, bj].
2. Пошук вершини vj з мінімальним значенням bj в мітці.
. Переразмечіваніе вершин, суміжних з vj
Всі ці функції є частиною ітеративного процесу пошуку, тобто можуть бути скомпоновані в рекурсивну функцію пошуку. У Пролог-програмі в ролі такої функції виступає предикат primeSearch/5, який пов'язує граф, безліч T, безліч S, список міток вершин і оптимальний каркас. Базовий випадок цього предиката (умова зупинки пошуку) - висловлювання, що приймає значення Істина, коли розмір безлічі T збігається з розміром безлічі вершин графа, тобто каркас охоплює всі вершини графа. Визначення даного предиката виглядає наступним чином:
primeSearch (graph (V, E), T, S, _, S): - length (V, L1), length (T, L2), L1 is L2.
primeSearch (graph (V, E), T, S, MN, Res):-primeMinimum (MN, par (X, Y)), remark (MN, E, X, D), primeSearch (graph (V, E), [X | T], [edge (X, Y) | S], D, Res).
Як можна бачити, граф представлений у вигляді функтора, що зв'язує безліч вершин і безліч ребер графа. Ребро, у свою чергу, представлено функтором edge/2, зв'язує кінцеві вершини. Предикат реалізує п.3 і п.4 алгоритму
На виконання п.1 та п.2 визначено предикат primeInit, що визначає початкове зміст множин T і S, і здійснює первинну розмітку вершин графа, викликаючи предикат markerVx/4.
Предикат markerVx планований вершини згідно з правилом п.2, визначаючи для вершин, незв'язаних з початковою, значення bj досить велика, щоб вважати його нескінченним. Визначення предиката виглядає наступним чином:
([], _, _, []).
markerVx ([H | T], S, E, [X | XS]): - elem (edge ​​(H, S, W), E), X = mark (H, S, W), markerVx (T, S, E, XS).
markerVx ([H | T], S, E, [mark (H, S, 99999) | XS]): - not (elem (edge ​​(H, S, W), E) ), markerVx (T, S, E, XS).
Пошук додається ребра здійснює предикат primeMin. Цей предикат визначає пару вершин, перша з яких є не пренадлежали Ts вершиною з мінімальним значенням мітки b, а друга - певна міткою вершина, що належить каркасу. Визначення предиката:
...
