To DFS bolo z 1 vrcholu, takze sa to nemuselo robit pre cely graf. Ak by nahodou niekomu mohlo pomoct riesenie, tak:
Kód: Vybrat vše
% DFS z vrcholu
% g(V,E), V=[a,b,...] E=[e(a,b),...]
% prejdi(+ES,+E,+Vrchol,+KdeBol,-KdeBOlOut,+TIn,-TOut,-Zoz)
prejdi([],_,_,KB,KB,T,T,[]).
prejdi([e(A,B)|ES],E,Vrchol,KdeBol,KdeBolOut,TIn,TOut,Zoz):-
( A \= Vrchol;
( A=Vrchol, member(B,KdeBol) )
),
prejdi(ES,E,Vrchol,KdeBol,KdeBolOut,TIn,TOut,Zoz).
prejdi([e(A,B)|ES],E,Vrchol,KdeBol,KdeBolOut,TIn,TOut,Zoz):-
TIn1 is TIn + 1,
A = Vrchol,
not(member(B,KdeBol)),
prejdi(E,E,B,[B|KdeBol],KBO,TIn1,TOut1,Zoz1),
TOut2 is TOut1 + 1,
prejdi(ES,E,Vrchol,KBO,KdeBolOut,TOut2,TOut,Zoz2),
append(Zoz1,Zoz2,Zoz3),
Zoz = [B-(TIn1,TOut2)|Zoz3].
% dfs(+g(V,E),-Zoznam)
dfs(g([],_),[]).
dfs(g([A|_],E),Zoznam):-
prejdi(E,E,A,[A],_,0,T,Zoz),
T2 is T + 1,
Zoznam = [A-(0,T2)|Zoz].
Je to trocha upravene, a vypise to nie len cas vystupu ale aj cas vstupu. Zacina z 1. vrcholu.
Ako velky priklad bolo priblizne nieco taketo:
Distribuovany tvar polynomu viac premennych je dany zoznamom, obsahujucich absolutny clen a zoznam mocnin premennych pre dany clen.
Ulohou bolo dostat na vstupe zoznam premennych a polynom (s operaciamy plus, minus, krat a mocnina na prirodzene cislo), ktory trebalo previest na distribuovany tvar.
Na zaciatku sa mi to zdalo ako nieco nepochopitelne ale ked som sa nad tym zamyslel a Hric ukazal aj priklad, tak sa to celkom dalo a k mojmu riesenie v podstate ani nemal ziadne vyhrady
Ked tak este ten priklad, co ukazal:
Kód: Vybrat vše
premenne: [x, y, z]
polynom: ((x+3)*(y*z)^5)
dist. tvar: (abs - x, y, z)
1 - 1, 5, 5
3 - 0, 5, 5