мини|Pretraga u dubinu (primer stabla) Pretraga u dubinu (na engleskom Depth-first search - DFS) je algoritam za pretragu struktura podataka (stabla i grafova). Početak algoritma je u korenu stabla (kod grafa se neki čvor odredi za koren), a zatim se pretražuje duž svih grana koliko god je to moguće pre povratka u koren.
Francuski matematičar Charles Pierre Trémaux (19. vek) je istraživao verziju ovog algoritma za problem izlaska iz lavirinta.
Formalna definicija Obilazak započinje iz proizvoljnog zadatog čvora , korena pretrage u dubinu. Koren se označava kao posećen. Zatim se bira proizvoljni neoznačeni čvor 1, susedan sa , pa se iz čvora 1 rekurzivno startuje pretraga u dubinu. Iz nekog nivoa rekurzije izlazi se kad se naiđe na čvor u kome su svi susedi (ako ih ima) već označeni. Ako su u trenutku završetka pretrage iz 1, svi susedi čvora označeni, onda se pretraga za čvor završava. U protivnom, bira se sledeći proizvoljni neoznačeni sused 2 čvora , izvršava se pretraga polazeći od 2, itd.
Vremenska i prostorna analiza Vremenska i prostorna analiza pretrage u dubinu razlikuje se od područja primene samog algoritma. U teorijskom računarstvu obično se koristi za prolaske kroz cele grafove i za to je potrebno vreme linearno veličini grafa. Kod tih aplikacija je prostorna složenost velika jer se čuvaju čvorovi trenutne putanje, kao i skup već posećenih čvorova. U ovom slučaju su vremenska i prostorna složenost ista kao kod pretrage u širinu (BFS) i izbor koji od ova dva algoritma koristiti manje zavisi od složenosti a više od toga šta koji algoritam daje na kraju.
Primer Za sledeći graf:
200px
pretraga u dubinu počinje od čvora A, uz pretpostavku da se leve ivice biraju pre desnih ivica grafa i da pretraga pamti prethodno posećene čvorove pa ih neće ponavljati. Čvorovi će biti posećeni u sledećem redosledu: A, B, D, F, E, C, G. Grane kroz koje se prošlo formiraju Trémaux stablo, strukturu sa važnim primenama u teoriji grafova.
Isto pretraživanje bez pamćenja prethodno posećenih čvorova izgleda ovako: A, B, D, F, E, A, B, D, F, E, itd. zauvek, zapetljano u A, B, D, F, E ciklus. Ovakva pretraga nikad neće posetiti čvorove C i G.
Povratne vrednosti pretrage u dubinu Nakon pretrage u dubinu dobijamo odgovarajuće razapinjujuće stablo. U tom stablu postoje četiri vrste grana: grana stabla (povezuje oca sa sinom) povratna grana (povezuje potomka sa pretkom) direktna grana (povezuje pretka sa potomkom) poprečna grana (povezuje čvorove koji nisu srodnici u stablu)
Pseudokod algoritma Ulaz: graf G i njegov čvor v Izlaz: graf pretrage u dubinu 1 funkcija PretragaUDubinu(G,v): 2 označi v kao posećen 3 for sve grane e u G.obižnjeGrane(v) do 4 if grane e je neposećena then 5 w ← G.obižnjiČvor(v,e) 6 if čvor w je neposećen then 7 označi e kao posećen 8 rekurzivan poziv PretragaUDubinu(G,w) 9 else 10 označi e kao zadnju granu
Ne rekurzivna implementacija pretrage u dubinu: 1 funkcija PretragaUDubinu-iterativno(G,v): 2 označi v kao posećen 3 neka S bude stek 4 S.push(v) 5 while S nije prazan 6 t ← S.top 7 if t ono što tražimo: 8 return t 9 for sve grane e u G.obližnjeGrane(t) do 10 if grana e već označena 11 continue sa sledećom granom 12 w ← G.obližnjiČvor(t,e) 13 if čvor w nije otkriven i nije posećen 14 označi e kao ivicu stabla 15 označi w kao otkriven 16 S.push(w) 17 continue at 5 18 else if čvor w is otkriven 19 označi e kao zadnja ivica 20 else 21 // čvor w je posećen 22 označi e kao napred ili kros ivica 23 označi t kao posećen 24 S.pop()
Primene Neki algoritmi koji koriste pretragu u dubinu kao gradivni element: Pronalaženje povezanih komponenti Topološko sortiranje Pronalaženje dve (grane ili čvora) povezane komponente. Pronalaženje tri (grane ili čvora) povezane komponente. Pronalaženje mostova grafa Pronalaženje snažno-povezanih komponenti Rešavanje zagonetki sa samo jednim rešenjem (npr. lavirint) Generisanje lavirinata
Literatura Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. Knuth, Donald E. (1997), The Art Of Computer Programming Vol 1. 3rd ed, Boston: Addison-Wesley Goodrich, Michael T. (2001), Algorithm Design: Foundations, Analysis, and Internet Examples, Wiley Živković, Miodrag, Algoritmi, Matematički Fakultet u Beogradu
Категорија:Графовски алгоритми Категорија:Алгоритми претраживања