Алгоритм Прима нахождения оптимального каркаса
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
±ург, 2003. - 1104 с.: ил.
Кристофидес Н. Теория графов. Алгоритмический подход. М. ДМК Пресс, 2003. - 356 с., ил.
Приложение
elem(X, [X|_]).(X, [_|HS]) :- elem(X,HS).
(graph([V|VS], E), [V], [], XS) :- markerVx(VS, V, E, XS).
([], _, _, []).([H|T], S, E, [X|XS]) :- elem(edge(H,S,W), E), X = mark(H, S, W), markerVx(T, S, E, XS).([H|T], S, E, [mark(H, S, 99999)|XS]) :- not(elem(edge(H,S,W), E)), markerVx(T, S, E, XS).
([], M, par(X, Y)) :- M = mark(X, Y, _).([H|T], mark(X, Y, M), XS) :- H = mark(X1, Y1, Z1), Z1 < M, !, primeMin(T, H, XS).([H|T], X, XS) :- primeMin(T, X, XS).
(X, Res) :- primeMin(X, mark(0, 0, 99999), Res).
(graph(V, E), T, S, _, S) :- length(V, L1), length(T, L2), L1 is L2.(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).
([], _, _, []).([H|HS], E, X, TH) :- H = mark(X, _, _), remark(HS, E, X, TH).([H|T], E, X, [NH|TH]) :- H = mark(X1, X2, W), elem(edge(X1, X, W1), E), W1 < W, NH = mark(X1, X, W1), remark(T, E, X, TH).([H|T], E, X, [H|TH]) :- remark(T, E, X, TH).(X) :- X = graph(
[0,1,2],
[(0,1,1),(0,2,2),(1,0,1),(1,2,3),(2,0,2),(2,1,3)
]).
(X) :- X =(
[1,2,3,4,5,6,7],
[(1,6,23),(1,7,1),(1,2,20),(2,1,20),(2,7,4),(2,3,15),(3,2,15),(3,7,9),(3,4,3),(4,3,3),(4,7,16),(4,5,17),(5,4,17),(5,7,25),(5,6,28),(6,5,28),(6,7,36),(6,1,23),(7,1,1),(7,2,4),(7,3,9),
edge(7,4,16),(7,5,25),(7,6,36)
]).
:- g2(X), primeInit(X, T, S, M), primeSearch(X, T, S, M, R), write(Graph optimal carcas : ), writeln(R).