Priporočena, 2024

Izbira Urednika

Razlika med BFS in DFS

Glavna razlika med BFS in DFS je v tem, da BFS napreduje po nivojih, medtem ko DFS sledi prvi poti od začetka do končnega vozlišča (vertex), nato pa še drugo pot od začetka do konca in tako naprej, dokler niso vsa vozlišča obiskana. Poleg tega BFS uporablja čakalno vrsto za shranjevanje vozlišč, medtem ko DFS uporablja stack za prečkanje vozlišč.

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
BFSDFS
OsnovnoVertex-based algoritemAlgoritem na osnovi robov
Struktura podatkov, ki se uporablja za shranjevanje vozliščČakalna vrstaStack
Poraba pomnilnikaNeučinkovitUčinkovito
Struktura zgrajenega drevesaŠiroka in kratkaOzka in dolga
Način prehodaNajprej se raziščejo najstarejše nepregledane točke.Na začetku se raziskujejo navpičnice vzdolž roba.
OptimalnostOptimalna za najkrajšo razdaljo, ne v ceno.Ni optimalno
UporabaPregleduje 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.

Aplikacije -

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.

Aplikacija

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

  1. BFS je vertex-based algoritem, medtem ko je DFS robni algoritem.
  2. V BFS se uporablja struktura podatkov o čakalni vrsti. Po drugi strani DFS uporablja sklad ali rekurzijo.
  3. Prostor pomnilnika se učinkovito uporablja v DFS, medtem ko izkoriščenost prostora v BFS ni učinkovita.
  4. BFS je optimalni algoritem, medtem ko DFS ni optimalen.
  5. 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.

Top