Pretrage “najpre u dubinu” (engleski depth first search, skraćeno DFS) i “najpre u širinu” (engleski breadth first search, skraćeno BFS) su često korišćene tehnike u rešavanju algoritamskih problema. Evo jednog, krajnje uopštenog opisa problema koji se mogu rešavati ovim algoritmima.
Neka je dat skup nekakvih stanja S i skup poteza P pomoću kojih se može preći iz jednog stanja u drugo. Stanje s[0] iz S je označeno kao polazno, a jedno ili više stanja kao završno. Završno stanje ili stanja mogu biti zadata i uslovom koji treba da ispune, umesto da budu zadata eksplicitno. Zadatak je da se pronađe niz poteza p[1], p[2], … p[n], takav da se potezom p[1] prelazi iz stanja s[0] u neko stanje s[1], potezom p[2] se prelazi iz s[1] u s[2], itd. a poslednjim potezom se prelazi u neko od završnih stanja.
U ovoj lekciji je objašnjena osnovna ideja jedne i druge pretrage na jednostavnim i poznatim primerima, kao što su problem 8 dama (samo DFS) i traženje puta u lavirintu (DFS i BFS).
Problem 8 dama sastoji se u tome da se na šahovsku tablu postavi 8 dama koje se međusobno ne napadaju. U ovom problemu svaka pozicija sa nekoliko postavljenih dama koje se ne napadaju predstavlja jedno moguće stanje. Početno stanje je prazna tabla, a završna stanja su sve pozicije sa 8 dama. Potez je dodavanje jedne dame na tablu tako da ona ne napada ranije postavljene dame. Ovde se, dakle, traži bilo koji niz od 8 poteza (jer svaki niz od 8 poteza dovodi do jedne završne pozicije).
U problemu izlaska iz lavirinta, lavirint je zadat matricom. Stanja su zadata koordinatama polja na kojima se nalazimo, potezi predstavljaju prelazak na susedno slobodno polje. Početno stanje je zadato poljem na kome se nalazimo na početku, a završno stanje – izlazom iz lavirinta, odnosno ciljem.
Ova lekcija se bavi algoritmima BFS i DFS na način koji ne zahteva bilo kakvo predznanje o grafovima. Ipak, da bismo izbegli moguće zablude i nesporazume, samo u ovom uvodnom tekstu, pomenućemo ukratko grafove i vezu ovih algoritama sa grafovima.
Pomenuta stanja i potezi opisuju jedan graf (stanja predstavljaju čvorove grafa, a potezi predstavljaju grane). Prema tome, uopšteni problem se može izraziti i ovako: potrebno je pronaći putanju u grafu od početnog čvora (stanja) do jednog (na primer do svakog, do najbližeg, do bilo kojeg…) od završnih čvorova. Zato se algoritmi BFS i DFS najčešće opisuju kao algoritmi pretrage grafova. U širem smislu reči, to jeste tačno. Međutim, graf koji se pretražuje može biti samo implicitan, a to i jeste slučaj u ovoj lekciji. To znači da graf možemo eventualno pominjati pri opisivanju problema, ali se graf ne kreira i ne koristi kao takav u algoritmu rešenja.