Pretraga u dubinu

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.

Pretraga u dubinu (primer stabla)

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 $r$, korena pretrage u dubinu. Koren se označava kao posećen. Zatim se bira proizvoljni neoznačeni čvor $r$₁, susedan sa $r$, pa se iz čvora $r$₁ 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 $r$₁, svi susedi čvora $r$ označeni, onda se pretraga za čvor $r$ završava. U protivnom, bira se sledeći proizvoljni neoznačeni sused $r$₂ čvora $r$, izvršava se pretraga polazeći od $r$₂, 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:

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:

1. grana stabla (povezuje oca sa sinom)
2. povratna grana (povezuje potomka sa pretkom)
3. direktna grana (povezuje pretka sa potomkom)
4. 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