Stromy, grafy Stromy: hledáni prvku in(X,T) Predikát in(X,T) uspěje, pokud se prvek X nachází ve stromu T. Prvek X se nachází ve stromě T, jestliže ■ Xje listem stromu T, jinak leaf(X) ■ Xje kořen stromu T, jinak tree(i_eft,x,Right) ■ Xje menší než kořen stromu T, pak se nachází v levém podstromu T, jinak ■ X se nachází v pravém podstromu T in(X, leaf(X)) :- !. in(X, tree(_,X,_)) :- !. in(X, tree(Left, Root, Right) ) :- XV, pak vznikne nový strom s kořenem V, vpravo má leaf(X) (vlevo je []) pokud T=leaf(V) a XV, pak v novém stromě L ponechej a X přidej doprava (rekurzivně) pokud T=tree(_,V,R) a XV, !. addOeaf(V), X, treeQeaf (X) ,V, []) ) :- !. add(tree(L,V,R), X, tree(L,V,Rl)) :- X>V, !, add(R,X,Rl). add(tree(L,V,R), X, tree(Ll,V,R)) :- add(L,X,LI). Hana Rudová, Logické programování 1,19. května 2010 Stromy, grafy Procházení stromů Napište predikát traverse(Tree, List), který projde traversálně strom Tree. Seznam List pak obsahuje všechny prvky tohoto stromu. Pořadí preorder: nejprve uzel, pak levý podstrom, nakonec pravý podstrom Procházení stromů ?- traverse(tree(treeOeaf (1) , 2 , treeOeaf (3) ,4,leaf(5))) ,6, tree(]eaf(7) ,8,leaf(9))) , [6,2,1,4, 3 , 5 ,8,7,9]) . (preorder) traverse(T,Pře):- t_pre(T,Pře,[]). t_pre([],S,S). t_pre(leaf(V) , [V|S] ,S) . t_pre(tree(L,V,R),[V|S],S2):- t_pre(L,S,Sl), t_pre(R,Sl,S2) . Použit princip rozdílových seznamů Hana Rudová, Logické programování I, 19. května 2010 6 / \ / \ / \ 2 8 % V=2, S=[1,4,3,5|S2] /\ /\ % S=[1|S1] 1 4 7 9 % S1=[4,3,5|S2] / \ 3 5 Stromy, grafy traverse(T,Pře):- t_pre(T,Pře,[]). t_pre([],S,S). t_pre(leaf(V),[V|S],S). t_pre(tree(L,V,R),[V|S],S2):- t_pre(L,S,Sl), t_pre(R,Sl,S2). 6 / \ / \ / \ 2 8 % V=2, S=[1,4,3,5|S2] / \ / \ % S=[1|S1] 1 4 7 9 % S1=[4,3,5|S2] / \ 3 5 Modifikuje algoritmus tak, aby byly uzly vypsány v pořadí inorder (nejprve levý podstrom, pak uzel a nakonec pravý podstrom), tj. [1,2,3,4,5,6,7,8,9] traverse(T,In):- t_in(T,In,[]). t_pre([],S,S). t_in(leaf(V) , [V|S] ,S) . t_in(tree(L,V,R),S,S2):- t_in(L,S,[V|S1]), t_in(R,Sl,S2). Hana Rudová, Logické programování I, 19. května 2010 6 Stromy, grafy DÚ: Procházení stromu postorder Modifikuje algoritmus tak, aby byly uzly vypsány v pořadí postorder (nejprve levý podstrom, pak pravý podstrom a nakonec uzel), tj. [1,3,5,4,2,7,9,8,6] traverse_post(T,Post):- t_post(T,Post,[]). t_pre([],S,S). t_post(leaf(V) , [V|S] ,S) . t_post(tree(l_,V,R) ,S,S2) :-t_post(L,S,Sl) , t_post(R,Sl,[V|S2]). 6 / \ / \ / \ 2 8 / \ / \ 14 7 9 / \ 3 5 Reprezentace grafu Reprezentace grafu: pole následníků uzlů Grafy nebudeme modifikovat, tj. pro reprezentaci pole lze využít term (Orientovaný) neohodnocený graf graf([2,3],[l,3],[l,2]). 1--2 \ I graf([2,4,6],[1,3],[2],[1,5],[4,6],[1,5]). 5— 4 I I 6- -1--2--3 Hana Rudová, Logické programování I, 19. května 2010 Stromy, grafy ?- functorCCraf,graf,PocetUzlu). ?- arg(Uzel,Graf.Sousedi). 1 (Orientovaný) ohodnocený graf [Soused-Ohodnoceni|Sousedi] graf([2-l,3-2],[1-1,3-2],[1-2,2-2]). grafC[2-1,4-3,6-1],[1-1,3-2],[2-2],[1-3,5-1],[4-1,6-2],[1-1,5-2]). Hana Rudová, Logické programování I, 19. května 2010 8 Stromy, grafy Procházení grafu do hloubky Napište predikát dfs(Uzel,Craf,Parents) pro procházení grafu Graf do hloubky z uzlu Uzel. Výsledkem je datová struktura Parents, která reprezentuje strom vzniklý při prohledávání do hloubky (pro každý uzel stromu známe jeho rodiče). Datová struktura pro rodiče uzlů: ■ při reprezentaci rodičů lze využít term s aritou odpovídající počtu uzlů ■ iniciálně jsou argumentu termu volné proměnné ■ na závěr je v N-tém argumentu uložen rodič N-tého uzlu (iniciální uzel označíme empty) graf([2,3],[l,3],[l,2]). graf([2,4,6],[1,3],[2],[1,5],[4,6],[1,5]). 1--2 1—2 5—4 5 4 \ I \ II II \| \ 6--1--2--3 6--1--2--3 3 3 U=4: rodic(4, 1, 2, empty, 6, 1) U=2: rodič(2,empty,1) Hana Rudová, Logické programování I, 19. května 2010 9 Stromy, grafy Procházení grafu do hloubky: algoritmus I Procházení grafu z uzlu Uzel ■ Vytvoříme term pro rodiče (všichni rodiči jsou zatím volné proměnné) ■ Uzel Uzel má prázdného rodiče a má sousedy Sousedi ■ Procházíme (rekurzivně) všechny sousedy v Sousedi dfs(Uzel,Graf,Parents) :- functor(Graf,graf,Počet), functor(Parents,rodiče,Počet), arg(Uzel,Parents,empty), arg(Uzel,Graf.Sousedi) , prochazej_sousedy(Sousedi,Uzel,Graf,Parents) . Hana Rudová, Logické programování I, 19. května 2010 10 Stromy, grafy Procházení grafu do hloubky: algoritmus II Procházení sousedů uzlu Uzel (pokud Uzel nemá sousedy, tj. Sousedi=[], končíme) 1. Uzel Vje první soused 2. Zjistíme rodiče uzlu V ... pomocí arg(V,Parents,Rodič) 3. Pokud jsme V ještě neprošli (tedy nemá rodiče a platí var(Rodic)), tak (a) nastavíme rodiče uzlu V na Uzel (b) rekurzivně procházej všechny sousedy uzlu V 4. Procházej zbývající sousedy uzlu Uzel prochazej_sousedy([],_,_,_). prochazej_sousedy([V|T],Uzel,Graf,Parents) :- arg(V,Parents,Rodič), ( nonvar(Rodic) -> true ; Rodič = Uzel , arg(V,Graf.SousediV), prochazej_sousedy(SousediV,V,Graf,Parents) ), prochazej_sousedy(T,Uzel,Graf,Parents). Hana Rudová, Logické programování I, 19. května 2010 Stromy, grafy DÚ: Procházení grafu do šířky Napište predikát bfs(U,C,P) pro procházení grafu C do šířky z uzlu U. Výsledkem procházení je datová struktura P, která reprezentuje strom vzniklý při prohledávání grafu C do šířky (pro každý uzel stromu známe jeho rodiče). graf([2,3],[l,3],[l,2]). graf([2,4,6],[1,3],[2],[1,5],[4,6],[1,5]). 1--2 1--2 5—4 \ I I II \| | 6--1--2--3 3 3 U=2: rodic(2,empty,2) 5— 4 I 6- -1--2--3 U=4: rodic(4, 1, 2, empty, 1) Hana Rudová, Logické programování 1,19. května 2010 Stromy, grafy