Razlika između BFS i DFS

BFS vs DFS

Prva pretraga širine (poznata i kao BFS) metoda je pretraživanja koja se koristi za proširivanje svih čvorova određenog grafa. Taj zadatak ispunjava pretraživanjem svakog pojedinog rješenja kako bi ispitao i proširio ove čvorove (ili kombinaciju nizova u njima). Kao takav, BFS ne koristi heuristički algoritam (ili algoritam koji traži rješenje putem više scenarija). Nakon što se dobiju svi čvorovi, oni se dodaju u red koji je poznat kao Red In, First Out. Oni čvorovi koji nisu istraženi spremljeni su u spremnik označen s "otvoren"; Jednom istraženi transportiraju se u kontejner označen kao "zatvoren".

Dubinska prva pretraga (poznata i kao DFS) metoda je pretraživanja koja se dublje provlači u podređeni čvor pretraživanja dok se ne postigne cilj (ili dok ne postoji čvor bez ikakvih drugih permutacija ili 'djece'). Nakon što je pronađen jedan cilj, povratno pretraživanje vraća na prethodni čvor koji je pronađen s rješenjem, ponavljajući postupak sve dok se svi čvorovi uspješno ne pretraže. Kao takav, čvorovi se i dalje stavljaju u stranu za daljnja istraživanja - to se naziva ne-rekurzivna implementacija.

Značajke BFS-a su složenost prostora i vremena, cjelovitost, dokaz potpunosti i optimalnosti. Svemirska složenost odnosi se na omjer broja čvorova na najdubljoj razini pretraživanja. Vremenska složenost odnosi se na stvarni iznos "vremena" koji se koristi za razmatranje svakog puta koji će čvor potrajati u pretraživanju. Kompletnost je, u osnovi, pretraga koja pronalazi rješenje u grafikonu bez obzira na to o kojoj vrsti je grafa. Dokaz cjelovitosti je najplića razina na kojoj se cilj nalazi u čvoru na određenoj dubini. Napokon, optimalnost se odnosi na BFS koji nije ponderiran - to je graf koji se koristi za jedinični trošak.

DFS je najprirodniji rezultat pomoću raspoređenog stabla - što je stablo sastavljeno od svih vrhova i nekih rubova u neizravnom grafu. U ovoj formaciji graf je podijeljen u tri klase: Naprijed rubovi, koji pokazuju od čvora do podređenog čvora; stražnji rubovi, usmjereni od čvora do ranijeg čvora; i poprečnim rubovima, koji ne čine nijedan od ovih.

Sažetak:

1. BFS pretražuje svako pojedinačno rješenje u grafikonu kako bi proširio svoje čvorove; DFS se zakopa duboko u podređenom čvoru dok se ne postigne cilj.

2. Značajke BFS-a su složenost prostora i vremena, cjelovitost, dokaz potpunosti i optimalnosti; najprirodniji rezultat za DFS je raspoređeno stablo s tri klase: prednje ivice, stražnje i poprečne.