Numărul de componente conexe într-un graf.
Enunț:
Se dă un graf nedirecționat: se dă lista vârfurilor sale și pentru fiecare vârf se dă lista
vecinilor săi. Se cere un program Prolog care să afle și să afișeze numărul de componente conexe din graful dat.
% definirea grafurilor pentru teste
graf1:-abolish(nodes),abolish(vec),
asserta(nodes([a,b,c,d,e,f,g,h])),
asserta(vec(a,[b,c])),
asserta(vec(b,[a])),
asserta(vec(c,[a,d,e])),
asserta(vec(d,[c])),
asserta(vec(e,[c])),
asserta(vec(f,[g,h])),
asserta(vec(g,[f,h])),
asserta(vec(h,[f,g])).
graf2:-abolish(nodes),abolish(vec),
asserta(nodes([a,b,c,d,e,f,g,h,i,j,k,l,m])),
asserta(vec(a,[b,c,h])),
asserta(vec(b,[a])),
asserta(vec(c,[a])),
asserta(vec(d,[k,m])),
asserta(vec(e,[i,g])),
asserta(vec(f,[i,g])),
asserta(vec(g,[e,f])),
asserta(vec(h,[a])),
asserta(vec(i,[j,e,f])),
asserta(vec(j,[i,k])),
asserta(vec(k,[d,j])),
asserta(vec(l,[])),
asserta(vec(m,[d])).
% testele
test1:-graf1,comp.
test2:-graf2,comp.
% programul
comp:-clear,init,loop,write_res.
init:-nodes(L),init(L).
init(L):-assert(total(0)),list_noduri(L).
clear:-clear_coada,nodes(L),clear(L).
clear(L):-retract(total(X)),clear(L).
clear([X|L]):-retract(liber(X)),clear(L).
clear(L).
clear_coada:-retract(coada(X)),clear_coada.
clear_coada.
write_res:-retract(total(X)),write(X).
list_noduri([X]):-assert(liber(X)).
list_noduri([X|Y]):-assert(liber(X)),list_noduri(Y).
% simulam un ciclu
loop:-retract(liber(X)),push(X),parcurge,retract(total(T)),T1 is T+1,assert(total(T1)),loop.
loop.
parcurge:-pop(X),vec(X,V),get_free(V,L),push(L),parcurge.
parcurge.
get_free([],[]).
get_free([X|L],[X|K]):- retract(liber(X)),get_free(L,K).
get_free([X|L],K):- get_free(L,K).
get_free(X,[X|K]):- retract(liber(X)).
get_free(X,K).
% simulam coada de noduri atinse in componenta curenta
push([]).
push([X]):-push(X).
push([X|L]):-push(X),push(L).
push(X):-assert(coada(X)).
pop(X):-retract(coada(X)).
Interogări:
?- test1.
2
?- test2.
3
Cel mai scurt drum între 2 vârfuri într-un graf.
Enunț:
Se dă un graf nedirecționat: se dă lista vârfurilor sale și lista de muchii sub forma (a,b,c),
unde a și b sunt vârfurile muchiei și c este costul ei.
Se cere un program Prolog care să afle și să afișeze cel mai scurt drum de la un vârf S la
un vârf F în graful dat.
% definirea grafurilor utilizate
graf1:-abolish(nodes),abolish(vec),
assert(nodes([a,b,c,d,e])),
assert(vec(a,b,10)),
assert(vec(b,c,10)),
assert(vec(c,d,15)),
assert(vec(a,d,23)),
assert(vec(c,e,5)),
assert(vec(d,e,10)).
graf2:-abolish(nodes),abolish(vec),
assert(nodes([a,b,c,d,e,f,g,h])),
assert(vec(a,b,5)),
assert(vec(a,d,6)),
assert(vec(a,g,4)),
assert(vec(b,f,3)),
assert(vec(c,d,3)),
assert(vec(c,f,6)),
assert(vec(e,f,3)),
assert(vec(e,g,2)),
assert(vec(e,h,2)),
assert(vec(f,h,1)).
% testele
test1:-graf1,drum(a,c).
test2:-graf1,drum(d,b).
test3:-graf1,drum(a,e).
test4:-graf2,drum(b,e).
test5:-graf2,drum(h,b).
test6:-graf2,drum(d,e).
test7:-graf2,drum(a,h).
% functii pentru muchii
is_connect(X,Y):-vec(X,Y,_);vec(Y,X,_).
cost(X,Y,Z):-vec(X,Y,C),Z is C;vec(Y,X,C),Z is C.
% initializare
clear:-nodes(L),clear_vl(L),clear_prec,clear_best(L),(retract(dst(X))->true;true).
clear_vl([X|L]):-set_vl(X,0),clear_vl(L).
clear_vl([]).
clear_best([X|L]):-set_best(X,1000000),clear_best(L).
clear_best([]):-set_best(z,1000000).
clear_prec:-abolish(prec).
clear_prec.
init(S):-set_vl(S,1),set_best(S,0).
drum(S,F):-clear,init(S),loop(F),get_best(F,Res),afiseaza_drum(S,F),write(‘\nLungimea
drumului – ‘),write(Res).
loop(F):-get_min(F) ; get_min(X), ( get_best(X,1000000) ; set_vl(X,2), update(X) ,
loop(F) ) .
afiseaza_drum(S,S):-write(S).
afiseaza_drum(S,F):-get_prec(F,X),afiseaza_drum(S,X),write(-),write(F).
% —
get_min(X):-nodes(L),get_free_node(Y),get_min(Y,L,X).
get_min(X,[Y|L],X):-
get_vl(Y,C),C==1,get_best(Y,BY),get_best(X,BX),BY<BX,get_min(X,L,X).
get_min(X,[Y|L],Z):- get_min(X,L,Z).
get_min(X,[],X).
get_free_node(X):-nodes(L),get_free_node(X,L).
get_free_node(Y,[Y|L]):-get_vl(Y,V),V==1.
get_free_node(X,[Y|L]):-get_free_node(X,L).
% —
update(X):-nodes(L),update(X,L).
update(X,[Y|L]):- ( X\==Y, get_best(X,BX) , get_vl(Y,VY) , cost(X,Y,C) , CCost is
BX+C , get_best(Y,BY) , (VY==0 ; VY==1 , CCost<BY) , set_vl(Y,1),
set_best(Y,CCost), set_prec(Y,X) ; true ) , update(X,L).
update(X,[]).
% —
set_vl(X,Y):-retract(vl(X,Z)),assert(vl(X,Y));assert(vl(X,Y)).
get_vl(X,Y):-retract(vl(X,Y)),assert(vl(X,Y)).
set_best(X,Y):-retract(best(X,Z)),assert(best(X,Y));assert(best(X,Y)).
get_best(X,Y):-retract(best(X,Y)),assert(best(X,Y)).
% seteaza Y ca nodul precedent al lui X
set_prec(X,Y):-retract(prec(X,Z)),assert(prec(X,Y));assert(prec(X,Y)).
get_prec(X,Y):-retract(prec(X,Y)),assert(prec(X,Y)).
Interogări:
?- test1.
a-b-c
Lungimea drumului – 20
yes
?- test2.
d-a-b
Lungimea drumului – 33
yes
?- test3.
a-b-c-e
Lungimea drumului – 25
yes
?- test4.
b-f-e
Lungimea drumului – 6
yes
?- test5.
h-f-b
Lungimea drumului – 4
yes
?- test6.
d-c-f-e
Lungimea drumului – 12
yes
?- test7.
a-b-f-h
Lungimea drumului – 9
yes
InfoCad Blog 