Pretraga u dubinu

Из Википедије, слободне енциклопедије
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 r, korena pretrage u dubinu. Koren se označava kao posećen. Zatim se bira proizvoljni neoznačeni čvor r1, susedan sa r, pa se iz čvora r1 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 r1, svi susedi čvora r označeni, onda se pretraga za čvor r završava. U protivnom, bira se sledeći proizvoljni neoznačeni sused r2 čvora r, izvršava se pretraga polazeći od r2, 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:

Graph.traversal.example.svg


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              wG.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            tS.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               wG.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()

Aplikacije[уреди]

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