Kakšna je razlika med BFS in DFS - Razlika Med

Kakšna je razlika med BFS in DFS

The glavna razlika med BFS in DFS BFS ali prvo iskanje po korakih se nadaljuje po nivoju, medtem ko DFS ali globina prvega iskanja sledi poti od začetnega do končnega vozlišča in se nato premakne na drugo pot od začetka do konca in tako naprej, dokler ne obišče vseh vozlišč.

Graf je nelinearna podatkovna struktura, ki ureja podatkovne elemente kot mrežni model. Vozlišča v grafu se imenujejo vertices, robovi pa povezujejo ta vozlišča. Večino težav z grafom je mogoče rešiti z metodami iskanja. Prvo iskanje po širini (BFS) in prvo iskanje po globini (DFS) sta običajni iskalni metodi, ki se uporabljata. Na kratko, BFS uporablja čakalno vrsto, medtem ko DFS uporablja stack.

Pokrita ključna območja

1. Kaj je BFS
- Opredelitev, funkcionalnost
2. Kaj je DFS
- Opredelitev, funkcionalnost
3. Kakšna je razlika med BFS in DFS
- Primerjava ključnih razlik

Ključni pogoji

BFS, DFS


Kaj je BFS

BFS pomeni Najprej dihanje. Uporablja čakalno vrsto. Postopek je naslednji.

  • Obiščite začetno točko in postavite ta element v čakalno vrsto.
  • Večkrat odstranite vozlišče iz čakalne vrste, ki obišče nevidne sosednje točke.
  • Novo obiskano točko postavite v čakalno vrsto.

Primer je naslednji.


Slika 1: BFS

Predpostavimo, da je začetna točka na zgornji sliki 1. Vozlišča, povezana z 1, so 2 in 4. Tako lahko postavimo 1, 2 in 4 v čakalno vrsto. Izhod je 1, 2, 4. Za 1 ni preostalih tock. Zato lahko iz čakalne vrste odstranimo 1. Zdaj se lahko premaknemo na 2. Sosednja tocka 2 sta 3, 5 in 6. Tako lahko postavimo 3, 5 in 6 v vrsto. Izhod je 1, 2, 4, 3, 6. Poleg teh treh števil, ni sosednjih vozlišč, ki bi bile povezane z 2. Torej lahko iz reda odstranimo 2. Sedaj se premaknimo na 4. Edino sosednje vozlišče do 4 je 6. Obiskano je že bilo. Za 4. ni več vozlišč. Zato lahko odstranimo 4 iz čakalne vrste. Ta postopek morate ponoviti, dokler ni čakalna vrsta prazna. Označuje zaključek iskalne operacije.

Kaj je DFS

DFS pomeni Globina prvega iskanja. Postopek je naslednji.

Obiščite sosednje neveščane točke in jih označite kot obiskano. Nato ga prikažite na izhodu in ga potisnite v sklad.

Če ni najdenega sosednjega vozlišča, popupite vrh iz skladovnice.

Nadaljujte z dvema korakoma, dokler sveženj ni prazen.


Slika 2: DFS

Začetna točka je A. Potisne se v sklad. Sosednja vozlišča so B in E. Razmislite o B. Lahko potisnemo B v sklad. Ker ni sosednjih vozlišč za B, lahko izstopimo iz stack. Izhod je A B. Preostalo sosednje vozlišče do A je E, tako da lahko E razširimo na stack. Zdaj je izhod A B E.

Ker ni sosednjih vozlišč za A, lahko izstopimo iz sklada. Sosednja vozlišča za E so C in H. Upoštevajmo C. Lahko pritisnemo C na sklad. Izhod je A B E C. Postopek se nadaljuje, dokler sveženj ni prazen. Konča iskanje.

Razlika med BFS in DFS

Opredelitev

BFS (prvo iskanje po širini) je algoritem prečkanja grafa, ki začne prehoditi graf iz korenskega vozlišča in raziskuje vsa sosednja vozlišča. DFS (prvo iskanje po globini) je algoritem, ki se začne z začetnim vozliščem grafa, nato pa gre globlje in globlje, dokler ne najde zahtevanega vozlišča ali vozlišča, ki nima otrok. To je torej glavna razlika med BFS in DFS.

Dolga oblika

Medtem ko BFS pomeni »Širina prvega iskanja«, DFS pomeni »Depth First Search«.

Metoda shranjevanja vozlišč

Druga velika razlika med BFS in DFS je, da BFS uporablja čakalno vrsto, medtem ko DFS uporablja stack.

Poraba pomnilnika

Poleg tega BFS porabi več pomnilnika kot DFS.

Način prehoda

Metoda tranversinga je še ena razlika med BFS in DFS. BFS se najprej osredotoči na obisk najstarejših neprisotnih tock, medtem ko se DFS osredotoca na obisk tock po robu na zacetku.

Zaključek

BFS in DFS sta iskalni metodi za iskanje elementa v grafu. Glavna razlika med BFS in DFS je v tem, da BFS napreduje po ravni, medtem ko DFS sledi poti od začetnega do končnega vozlišča in se nato premakne na drugo pot od začetka do konca in tako naprej, dokler ne obišče vseh vozlišč.

Sklic:

1. Algoritem za prvo iskanje po širini Kodeks | Uvod, izobraževanje 4u, 22. marec 2018,