Stromy, grafy Stromy: hledáni prvku in(X.Tree) Napište predikát in(X,Tree), který uspěje, pokud se prvek X nachází v Tree. 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 má nový strom kořen V a vpravo se nachází 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í I, 28. dubna 2009 Stromy, grafy Procházení stromů Napište predikát traverse(Tree, List), který projde traversálně strom Tree a v seznamu List pak obsahuje všechny prvky tohoto stromu. Pořadí preorder: nejprve uzel, pak levý podstrom, nakonec pravý podstrom (preorder) 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]) 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, 28. dubna 2009 6 / \ / \ / \ 2 8 % V=2, S=[l,4,3,5|: /\ /\ % S=[1|S1] 14 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, 28. dubna 2009 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, 28. dubna 2009 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, 28. dubna 2009 8 Stromy, grafy Procházení grafu do hloubky Napište predikát dfs(U,C,P) pro procházení grafu C do hloubky z uzlu U. Výsledkem procházení je datová struktura P, 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],[1,3],[1,2]). graf([2,4,6],[1,3],[2],[1,5], [4,6], [1,5]) . 1--2 1—2 \ I \ \l \ 3 3 U=2: rodič(2,empty,1) Hana Rudová, Logické programování I, 28. dubna 2009 5- -4 I I 6- -1--2--3 5 4 I I 6--1--2--3 U=4: rodič(4, 1, 2, empty, 6, Stromy, grafy Procházení grafu do hloubky: algoritmus I Procházení grafu z uzlu U ■ Vytvoříme term pro rodiče (všichni rodiči jsou zatím volné proměnné) ■ Uzel U má prázdného rodiče a má sousedy S ■ Procházíme (rekurzivně) všechny sousedy v S dfs(U,G,P) :- f unctor(C,graf,Počet), functor(P,rodiče,Počet) , arg(U,C,Sousedi), arg(U,P,empty), prochazej_sousedy(Sousedi,U,C,P). Hana Rudová, Logické programování I, 28. dubna 2009 Stromy, grafy Procházení grafu do hloubky: algoritmus II Procházení sousedů S uzlu U 1. Uzel Vje první soused 2. Zjistíme rodiče uzlu V 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 U (b) rekurzivně procházej všechny sousedy uzlu V 4. Procházej zbývající sousedy uzlu U prochazej_sousedy([],_,_,_). prochazej_sousedy([V|T],U,C,P) :- arg(V,P,Rodič), ( nonvar(Rodic) -> ; Rodič = U, arg(V,C,SousediV), prochazej_sousedy(Sousedi V,V,C,P) ), prochazej_sousedy(T,U,C,P). Hana Rudová, Logické programování I, 28. dubna 2009 11 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,4,6],[1,3],[2],[1,5],[4,6],[1,5]). graf([2,3],[l,3],[l,2]). 1--2 1--2 \ I I \l I 3 3 U=2: rodic(2,empty,2) 5--4 5--4 I I I 6__!__2--3 6--1--2 —3 U=4: rodič(4, 1, 2, empty, 4, Hana Rudová, Logické programováni I, 28. dubna 2009 Stromy, grafy