BFS in DFS sta prehodni metodi, ki se uporabljata pri iskanju grafa. Prečkanje grafa je proces obiska vseh vozlišč grafa. Graf je skupina V 'V' in robov 'E', ki se povezujeta z vozlišči.
Primerjalna tabela
| Podlaga za primerjavo | BFS | DFS |
|---|---|---|
| Osnovno | Vertex-based algoritem | Algoritem na osnovi robov |
| Struktura podatkov, ki se uporablja za shranjevanje vozlišč | Čakalna vrsta | Stack |
| Poraba pomnilnika | Neučinkovit | Učinkovito |
| Struktura zgrajenega drevesa | Široka in kratka | Ozka in dolga |
| Način prehoda | Najprej se raziščejo najstarejše nepregledane točke. | Na začetku se raziskujejo navpičnice vzdolž roba. |
| Optimalnost | Optimalna za najkrajšo razdaljo, ne v ceno. | Ni optimalno |
| Uporaba | Pregleduje dvodelni graf, povezano komponento in najkrajšo pot v grafu. | Pregleda povezan robni graf, močno povezan graf, aciklični graf in topološki vrstni red. |
Opredelitev BFS
Prva širina iskanja (BFS) je metoda prehoda, ki se uporablja v grafih. Za shranjevanje obiskanih vozlišč uporablja čakalno vrsto. Pri tej metodi je poudarek na tockah grafa, najprej se izbere ena tocka, nato se obiskuje in oznaci. Točke, ki ležijo ob obiskanem vozlišču, so nato obiskane in shranjene v čakalni vrsti zaporedno. Podobno se shranjena vozlišča nato obravnavajo ena po ena in obiskujejo sosednja vozlišča. Vozlišče je v celoti raziskano pred obiskom katerega koli drugega vozlišča v grafu, z drugimi besedami, najprej najprehodno nepreverjena vozlišča.
Primer
Imamo graf, katerega tocki so A, B, C, D, E, F, G. Upoštevanje A kot izhodišca. Postopki, ki so vključeni v postopek, so:
- Vertex A se razširi in shrani v čakalno vrsto.
- Vertices B, D in G nasledniki A, so razširjeni in shranjeni v čakalni vrsti, medtem ko je Vertex A odstranjen.
- Sedaj je B na sprednjem koncu čakalne vrste odstranjen skupaj s shranjevanjem njegovih naslednikov vozlišč E in F.
- Vrstica D je na sprednjem koncu čakalne vrste in odstranjena je njena povezana vozlišča F.
- Vertex G se odstrani iz čakalne vrste in ima naslednika E, ki je že obiskan.
- Zdaj se E in F odstranita iz čakalne vrste in njena naslednica vozlišča C se prečka in shrani v čakalno vrsto.
- Končno je tudi C odstranjen in čakalna vrsta je prazna, kar pomeni, da smo končali.
- Ustvarjeni izhod je - A, B, D, G, E, F, C.
BFS je lahko koristen pri ugotavljanju, ali ima graf povezane komponente ali ne. Prav tako se lahko uporablja pri odkrivanju bipartitnega grafa .
Graf je bipartiten, kadar so vozlišča grafa razdeljena na dva ločena niza; v istem nizu ne bosta dve sosednji tocki. Druga metoda preverjanja bipartitnega grafa je preverjanje pojavnosti nenavadnega cikla v grafu. Dvodelni graf ne sme vsebovati nenavadnega cikla.
BFS je tudi boljši pri iskanju najkrajše poti v grafu, ki se lahko vidi kot omrežje.
Opredelitev DFS
Način prečkanja globine prvega iskanja (DFS) uporablja sklad za shranjevanje obiskanih vozlišč. DFS je metoda, ki temelji na robovih in deluje na rekurzivni način, kjer so točke pregledane vzdolž poti (roba). Raziskovanje vozlišča je začasno ustavljeno takoj, ko je najdeno še eno neraziskano vozlišče in se najprej prečkajo najgloblje nepreučene vozlišča. DFS prečkate / obiščete vsako točko natančno enkrat in vsak rob se natančno pregleda dvakrat.
Primer
Podobno kot pri BFS omogoča, da za izvedbo operacij DFS uporabite isti graf, pri čemer so vključeni naslednji koraki:
- Upoštevajoč A kot začetno točko, ki se raziskuje in shrani v sklad.
- B naslednik vrh A je shranjen v sklad.
- Vertex B ima dva naslednika E in F, med njimi po abecedi E je najprej raziskan in shranjen v sklad.
- Naslednik vozlišča E, tj. G, je shranjen v skladu.
- Vertex G imata dve povezani tocki in oba sta že obiskana, tako da je G izpisan iz sklada.
- Podobno je tudi E s odstranjen.
- Zdaj je vrh B na vrhu kupa, njegovo drugo vozlišče (vertex) F pa je raziskano in shranjeno v skladu.
- Vrstica F ima dva naslednika C in D, med katerima je C najprej prečrtana in shranjena v sklad.
- Vertex C ima samo enega predhodnika, ki je že obiskan, zato je odstranjen iz sklada.
- Sedaj je vertex D, povezan z F, obiskan in shranjen v sklad.
- Ker tocka D nima neobiskanih vozlišc, je D odstranjena.
- Podobno so tudi F, B in A.
- Ustvarjeni izhod je - A, B, E, G, F, C, D.
Aplikacije DFS vključujejo pregled dveh robno povezanih grafov, močno povezanega grafa, acikličnega grafa in topološkega reda .
Graf se imenuje dva robova, ki sta povezana, če in samo če ostane povezana, tudi če je eden od njenih robov odstranjen. Ta aplikacija je zelo uporabna v računalniških omrežjih, kjer neuspeh ene povezave v omrežju ne bo vplival na preostalo omrežje in bo še vedno povezan.
Močno povezan graf je graf, v katerem mora obstajati pot med urejenim parom tock. DFS se uporablja v usmerjenem grafu za iskanje poti med vsakim urejenim parom tock. DFS lahko brez težav rešuje težave s povezljivostjo.
Ključne razlike med BFS in DFS
- BFS je vertex-based algoritem, medtem ko je DFS robni algoritem.
- V BFS se uporablja struktura podatkov o čakalni vrsti. Po drugi strani DFS uporablja sklad ali rekurzijo.
- Prostor pomnilnika se učinkovito uporablja v DFS, medtem ko izkoriščenost prostora v BFS ni učinkovita.
- BFS je optimalni algoritem, medtem ko DFS ni optimalen.
- DFS konstruira ozka in dolga drevesa. V nasprotju s tem BFS konstruira široko in kratko drevo.
Zaključek
BFS in DFS, obe tehniki iskanja grafov imata podoben čas delovanja, vendar drugačno porabo prostora, DFS sprejema linearni prostor, ker moramo zapomniti eno pot z neraziskanimi vozlišči, medtem ko BFS ohranja vsako vozlišče v spominu.
DFS prinaša globlje rešitve in ni optimalen, vendar deluje dobro, kadar je rešitev gosta, medtem ko je BFS optimalna, ki najprej išče optimalni cilj.
