Razlika med BFS VS DFS

Iskanje prve širine (BFS) in Prvo iskanje globine (DFS) sta dva pomembna algoritma, ki se uporabljata za iskanje. Prvo iskanje širine začne iskanje s prvega vozlišča in se nato premakne čez nivoje, ki je bližje korenskemu vozlišču, medtem ko algoritem globinsko iskanje začne s prvim vozliščem in nato dokonča svojo pot do končnega vozlišča ustrezne poti. Med iskanjem oba algoritma prečkata vsako vozlišče. Za oba algoritma so napisane različne kode za izvedbo postopka prehoda. Prav tako veljajo za pomembne algoritme iskanja v umetni inteligenci.

V tej temi bomo spoznali BFS VS DFS.

Kako delujeta BFS in DFS?

Spodaj je s primeri opisano delovanje mehanizma obeh algoritmov. Za boljše razumevanje uporabljenega pristopa jih prosite.

Primer iskanja po širini

  • 1. korak: N1 je korensko vozlišče, zato se bo začelo od tu. N1 je povezan s tremi vozlišči N2, N3 in N4. Vsa tri vozlišča še niso obiskana. Torej, začnemo z N2 in ga shranimo v čakalno vrsto. Torej, čakalna vrsta z imenom Q vsebuje samo N2.

V: N2

  • 2. korak: Nato je vozlišče, ki je povezano z N1, N3. Ker smo šli čez ali obiskali vozlišče, ga bomo shranili v čakalni vrsti. Torej, posodobljena čakalna vrsta je

V: N3, N2

  • 3. korak: Nato je vozlišče, ki je povezano s korenskim vozliščem, N4. Shranili ga bomo v čakalni vrsti.

V: N4, N3, N2

  • 4. korak: Vsa vozlišča, ki so povezana z N1, so shranjena v čakalni vrsti. Zdaj odstranimo N2 iz čakalne vrste po načelu First in First Out (FIFO) in poiščemo vozlišča, ki so povezana z N2, tj. N5. N5 ni obiskan enkrat, zato ga bomo shranili v čakalni vrsti.

V: N5, N4, N3

  • 5. korak: Obiskana so vsa točila, zato nadaljujemo z odstranjevanjem vozlišč iz čakalne vrste, dokler ni prazna.

Primer prvega globine iskanja

  • 1. korak: Začeli bomo z N1 kot začetno vozlišče in ga shranili v sveženj S. N1 je povezan s tremi sosednjimi vozlišči N2, N3 in N4. Začenši z N2 (lahko začnete abecedno ali številčno), bomo to postavili v sklad.

S: N2 (zgoraj), N1

  • 2. korak: Zdaj sta sosednji vozlišči N2 N1 in N5. Ker je N1 že prisoten v kupu, kar pomeni, da je obiskan, bomo zato vzeli N5 in ga dali v sklad S.

S: N5 (zgoraj), N2, N1

  • Korak 3: Zdaj sta sosednji vozlišči N5 N3 in N4. Začnemo bo N3 in ga damo v kup.

S: N3 (zgoraj), N5, N2, N1

Zdaj je N3 povezan z N5 in N1, ki sta že prisotni v sveženju, kar pomeni, da sta obiskana, zato bomo N3 iz sklada odstranili po načelu Last in First Out (LIFO).

S: N5 (zgoraj), N2, N1

  • 4. korak: Zdaj bomo postavili zadnje vozlišče, ki ga nismo našli v celotnem prehodu po N4, in ga postavili v kup.

S: N4 (zgoraj), N5, N2, N1

  • Korak 5: Zdaj nismo zapustili nobenih drugih vozlišč, zato bomo v skladovnici preverili, ali so v njem prisotna katera koli vozlišča, ki niso prisotna. Če so obiskana vsa povezana vozlišča, bomo odstranili vozlišča, prisotna v sveženju. N4 na primer nima povezovalnih vozlišč, ki jih nismo preverili, zato jih bomo odstranili iz sklada. Podobno lahko preverimo tudi za druga vozlišča. Algoritem se ustavi, ko je niz prazen.

Primerjava med podjetji BFS VS DFS (Infographics)

Spodaj je zgornjih 6 razlik med BFS VS DFS

Ključne razlike med BFS in DFS

Pogovorimo se o nekaterih glavnih ključnih razlikah med BFS in DFS

  • Iskanje prve širine (BFS) se začne od korenskega vozlišča in obišče vsa pripadajoča vozlišča, ki so nanj pritrjena, medtem ko se DFS začne s korenskim vozliščem in zaključi celotno pot, pripeto na vozlišče.
  • BFS sledi pristopu čakalne vrste, medtem ko DFS sledi pristopu Stacka.
  • Pristop, ki se uporablja v BFS, je optimalen, medtem ko postopek, ki se uporablja v DFS, ni optimalen.
  • Če je naš cilj najti najkrajšo pot, je BFS prednost pred DFS.

Primerjalna tabela BFS in DFS

Pogovorimo se o zgornji primerjavi med BFS in DFS

BFSDFS
Popolna oblika BFS je Breadth-First Search.Celotna oblika DFS je globinsko prvo iskanje
BFS je namenjen iskanju najkrajše razdalje in se začne od prvega ali korenskega vozlišča in se premika po vseh njegovih vozliščih, pritrjenih na zadevna vozlišča. Potem, ko boste prebrali spodnji primer, lahko dobite jasen pogled na njegov delovni mehanizem.DFS sledi globinskemu pristopu in zaključi celotno pot skozi vsa vozlišča, pritrjena na posamezno vozlišče. Potem, ko boste prebrali spodnji primer, lahko dobite jasen pogled na njegov delovni mehanizem.
Izvede se po načelu čakalne vrste, ki je pristop First In First Out (FIFO).Izvede se po načelu Stack, ki je pristop Last In First out (LIFO).
Vozlišča, ki so prečkana večkrat, se odstranijo iz čakalne vrste.Obiskana vozlišča so vstavljena v kup in kasneje, če ni več obiskanih vozlišč, se odstranijo.
Je sorazmerno počasnejši od globine prvega iskanja.Hitrejša je od algoritma Breadth-First Search.
Dodelitev pomnilnika je večja od algoritma globine prvega iskanja.Dodelitev pomnilnika je sorazmerno manjša od algoritma iskanja prvega kroga

Zaključek

Obstaja veliko aplikacij, kjer se zgornji algoritmi uporabljajo za strojno učenje ali iskanje rešitev, povezanih z umetno inteligenco itd. V glavnem se uporabljajo v grafih, da ugotovijo, ali je dvostranski ali ne, za zaznavanje ciklov ali komponent, ki so povezane. Prav tako veljajo za pomembne algoritme pri iskanju poti ali iskanju najkrajše razdalje. Glede na potrebe podjetja lahko uporabimo dva algoritma. Toda iskanje prvega širine velja za optimalen način, ne pa za algoritem globine prvega iskanja.

Priporočeni članki

To je vodnik za BFS VS DFS. Tukaj razpravljamo o ključnih razlikah BFS VS DFS z infografiko in primerjalno tabelo. Za več informacij si lahko ogledate tudi naslednje članke -

  1. Algoritem BFS
  2. TeraData proti Oracle
  3. Big Data vs Data Warehouse
  4. Big Data vs Apache Hadoop: Primerjava med 4 najboljšimi, ki se jih morate naučiti

Kategorija:

Razvoj programske opreme