BFS i DFS su načini prijelaza koji se koriste u pretraživanju grafikona. Prelazak grafa je proces posjećivanja svih čvorova grafikona. Graf je skup Vertices 'V' i Edges 'E' koji se povezuju s vrhovima.
Tablica usporedbe
| Osnova za usporedbu | BFS | DFS |
|---|---|---|
| Osnovni, temeljni | Vertex-based algoritam | Algoritam temeljen na rubovima |
| Struktura podataka koja se koristi za pohranu čvorova | Red | Stog |
| Potrošnja memorije | neefikasan | Učinkovit |
| Struktura izgrađenog stabla | Široka i kratka | Uske i duge |
| Način prijelaza | Najprije se istražuju najstariji nevidjeni vrhovi. | Vertices uz rub su istraženi u početku. |
| optimalnosti | Optimalno za pronalaženje najkraće udaljenosti, a ne u cijenu. | Nije optimalno |
| primjena | Ispituje bipartitni graf, povezanu komponentu i najkraći put koji se nalazi u grafu. | Ispituje povezan s dva ruba, čvrsto povezan graf, aciklički graf i topološki poredak. |
Definicija BFS-a
Breadth First Search (BFS) je metoda koja se koristi u grafovima. Ona koristi red za spremanje posjećenih vrhova. U ovoj metodi naglasak je na vrhovima grafa, najprije se odabire jedan vrh, a zatim ga se posjećuje i obilježava. Točke koje se nalaze u blizini posjećenog vrha se zatim posjećuju i pohranjuju u redu za redom. Slično tome, pohranjeni vrhovi se zatim tretiraju jedan po jedan, a njihove susjedne točke se posjećuju. Čvor je u potpunosti istražen prije posjeta bilo kojem drugom čvoru u grafikonu, drugim riječima, najprije prelazi najmanji neistraženi čvor.
Primjer
Imamo grafikon čiji su vrhovi A, B, C, D, E, F, G. Razmatrajući A kao polaznu točku. Koraci u procesu su:
- Vertex A je proširen i spremljen u red čekanja.
- Vertices B, D i G nasljednici A, prošireni su i pohranjeni u red čekanja dok je Vertex A uklonjen.
- Sada se B na prednjem kraju reda uklanja zajedno s pohranjivanjem njegovih nasljedničkih točaka E i F.
- Točka D se nalazi na prednjem kraju reda, a njegov povezani čvor F već je posjećen.
- Vertex G se uklanja iz reda čekanja i ima nasljednika E koji je već posjećen.
- Sada se E i F uklanjaju iz reda čekanja, a njegov sukcesivni vrh C se prelazi i sprema u red.
- Na kraju C se također uklanja i red je prazan što znači da smo gotovi.
- Generirani izlaz je - A, B, D, G, E, F, C.
BFS može biti koristan u pronalaženju da li grafikon ima spojene komponente ili ne. Također se može koristiti u otkrivanju bipartitnog grafa .
Graf je bipartitan kada su vrhovi grafova razdijeljeni u dva nepovezana skupa; ne postoje dva susjedna vrha u istom skupu. Druga metoda provjere bipartitnog grafa je provjera pojavljivanja neparnog ciklusa u grafu. Bipartitni graf ne smije sadržavati neparni ciklus.
BFS je također bolji u pronalaženju najkraćeg puta u grafu koji se može vidjeti kao mreža.
Definicija DFS-a
Način prijelaza dubine prvog pretraživanja (DFS) koristi stog za spremanje posjećenih vrhova. DFS je metoda temeljena na rubu i radi na rekurzivan način gdje se vertices istražuju uzduž putanje (rub). Istraživanje čvora je obustavljeno čim se pronađe još jedan neistraženi čvor, a najdublja neistražena čvorišta prelaze se prije svega. DFS prolazi / posjećuje svaki vrh točno jednom i svaki rub je pregledan točno dva puta.
Primjer
Slično BFS-u omogućuje korištenje istog grafikona za izvođenje DFS operacija, a uključeni koraci su:
- S obzirom na A kao početnu točku koja se istražuje i pohranjuje u stog.
- B sukcesivni vrh A pohranjen je u stog.
- Vertex B ima dva nasljednika E i F, među kojima je E najprije istražen i pohranjen u stog.
- Nasljednik vrha E, tj. G pohranjuje se u stog.
- Točka G ima dva povezana čvora, a oba su već posjećena, tako da je G izvučen iz stog.
- Isto tako, Es je također uklonjen.
- Sada se vrh B nalazi na vrhu stog, njegov drugi čvor (vrh) F se istražuje i pohranjuje u stog.
- Točka F ima dva nasljednika C i D, među kojima je C najprije prijeđena i pohranjena u snop.
- Vertex C ima samo jednog prethodnika koji je već posjećen, tako da je uklonjen iz stog.
- Sada je vrh D spojen na F posjećen i pohranjen u stog.
- Budući da vrh D nema nijedna neostvarena čvora, D je uklonjen.
- Isto tako, F, B i A su također izbačeni.
- Generirani izlaz je - A, B, E, G, F, C, D.
Primjena DFS-a uključuje pregled dvaju rubno povezanih grafova, čvrsto povezanih grafova, acikličkog grafa i topološkog reda .
Graf se naziva dva ruba povezana ako i samo ako ostane povezana čak i ako je jedan njezin rub uklonjen. Ova aplikacija je vrlo korisna, u računalnim mrežama gdje neuspjeh jedne veze u mreži neće utjecati na preostalu mrežu, i još uvijek će biti povezan.
Snažno povezan graf je graf u kojem mora postojati put između naručenog para vrhova. DFS se koristi u usmjerenom grafu za traženje putanje između svakog uređenog para vrhova. DFS može lako riješiti probleme s povezivanjem.
Ključne razlike između BFS-a i DFS-a
- BFS je vertex-based algoritam, a DFS je rubni algoritam.
- U BFS-u se koristi struktura podataka o čekanju. S druge strane, DFS koristi stog ili rekurziju.
- Memorijski prostor se učinkovito koristi u DFS-u, dok iskoristivost prostora u BFS-u nije učinkovita.
- BFS je optimalni algoritam, a DFS nije optimalan.
- DFS konstruira uska i duga stabla. Nasuprot tome, BFS konstruira široko i kratko drvo.
Zaključak
BFS i DFS, obje tehnike pretraživanja grafova imaju slično vrijeme rada, ali različitu potrošnju prostora, DFS uzima linearni prostor jer moramo zapamtiti jednu stazu s neistraženim čvorovima, dok BFS drži svaki čvor u memoriji.
DFS donosi dublja rješenja i nije optimalan, ali dobro radi kada je rješenje gusto, dok je BFS optimalan i najprije traži optimalni cilj.
