Kaj je BFS?
BFS je algoritem, ki se uporablja za grafikovanje podatkov ali iskanje dreves ali prehajanje struktur. Algoritem učinkovito obišče in na grafikonu natančno označi vsa ključna vozlišča.
Ta algoritem izbere posamezno vozlišče (začetno ali izvorno točko) v grafu in nato obišče vsa vozlišča, ki mejijo na izbrano vozlišče. Ko algoritem obišče in označi začetno vozlišče, se premakne proti najbližjim neobiskanim vozliščem in jih analizira.
Po obisku so vsa vozlišča označena. Te ponovitve se nadaljujejo, dokler niso vsa vozlišča grafa uspešno obiskana in označena. Celotna oblika BFS je iskanje po širini.
V tem BSF vs. DFS Binarno drevo vadnice, boste izvedeli:
- Kaj je BFS?
- Kaj je DFS?
- Primer BFS
- Primer DFS
- Razlika med binarnim drevesom BFS in DFS
- Aplikacije BFS
- Aplikacije DFS
Kaj je DFS?
DFS je algoritem za iskanje ali premikanje grafov ali dreves v smeri globine. Izvedba algoritma se začne na korenskem vozlišču in preuči vsako vejo pred povratnim sledenjem. Uporablja strukturo podatkovnega sklada, da si zapomni, pridobi naslednjo točko in začne iskanje, kadar koli se v kateri koli ponovitvi pojavi slepa ulica. Celotna oblika DFS je iskanje po globini.
Primer BFS
V naslednjem primeru DFS smo uporabili graf s 6 oglišči.
Primer BFS
Korak 1)
Imate graf sedmih številk v razponu od 0 - 6.
2. korak)
0 ali nič je bilo označeno kot korensko vozlišče.
3. korak)
0 je obiskano, označeno in vstavljeno v strukturo podatkov čakalne vrste.
4. korak)
Preostalih 0 sosednjih in neobiskanih vozlišč se obišče, označi in vstavi v čakalno vrsto.
5. korak)
Ponovitve ponovitve se ponavljajo, dokler niso obiskana vsa vozlišča.
Primer DFS
V naslednjem primeru DFS smo uporabili neusmerjeni graf s 5 oglišči.
Korak 1)
Začeli smo z oglišča 0. Algoritem se začne tako, da ga uvrstimo na obiskani seznam in hkrati postavimo vsa sosednja oglišča v podatkovno strukturo, imenovano sklad.
2. korak)
Obiskali boste element, ki je na vrhu sklada, na primer 1, in se pomaknili do sosednjih vozlišč. To je zato, ker je 0 že obiskano. Zato obiščemo točko 2.
3. korak)
Vertex 2 ima neobiskano bližnjo točko v 4. Zato jo dodamo v sklad in jo obiščemo.
4. korak)
Nazadnje bomo obiskali še zadnjo točko 3, v kateri ni nobenih neobiskanih sosednjih vozlišč. Prehod grafa smo zaključili z uporabo algoritma DFS.
Razlika med binarnim drevesom BFS in DFS
| BFS | DFS |
| BFS najde najkrajšo pot do cilja. | DFS gre na dno poddrevesa in nato nazaj. |
| Celotna oblika BFS je iskanje po širini. | Celotna oblika DFS je iskanje po globini. |
| Uporablja čakalno vrsto za beleženje naslednje lokacije za obisk. | Uporablja niz za sledenje naslednje lokacije za obisk. |
| BFS prečka glede na nivo drevesa. | DFS prečka glede na globino drevesa. |
| Izvaja se s pomočjo seznama FIFO. | Izvaja se z uporabo seznama LIFO. |
| Zahteva več pomnilnika v primerjavi z DFS. | Zahteva manj pomnilnika kot v primerjavi z BFS. |
| Ta algoritem daje rešitev plitke poti. | Ta algoritem ne zagotavlja najbolj plitke rešitve. |
| V BFS ni potrebe po povratnem sledenju. | V DFS obstaja potreba po povratnem sledenju. |
| Nikoli ne morete biti ujeti v končne zanke. | Lahko ste ujeti v neskončne zanke. |
| Če ne najdete nobenega cilja, boste morda morali razširiti veliko vozlišč, preden bo rešitev najdena. | Če ne najdete nobenega cilja, lahko pride do povratnega sledenja vozliščem listov. |
Aplikacije BFS
Tu so aplikacije BFS:
Netehtani grafi:
BFS algoritem lahko enostavno ustvari najkrajšo pot in minimalno drevo, ki v najkrajšem možnem času z visoko natančnostjo obišče vse točke grafa.
P2P omrežja:
BFS je mogoče uporabiti za iskanje vseh najbližjih ali sosednjih vozlišč v omrežju enakovrednih naprav. Tako boste hitreje našli zahtevane podatke.
Spletni pajki:
Iskalniki ali spletni pajki lahko z uporabo BFS enostavno zgradijo več stopenj indeksov. Izvajanje BFS se začne od vira, ki je spletna stran, in nato obišče vse povezave iz tega vira.
Omrežno oddajanje:
Oddani paket vodi algoritem BFS, da najde in doseže vsa vozlišča, za katera ima naslov.
Aplikacije DFS
Tu so pomembne aplikacije DFS:
Uteženi graf:
V tehtanem grafu prehod grafa DFS ustvari drevo najkrajše poti in najmanjše drevo.
Odkrivanje cikla v grafu:
Graf ima cikel, če smo med DFS našli zadnji rob. Zato bi morali za grafikon zagnati DFS in preveriti zadnje robove.
Iskanje poti:
Za iskanje poti med dvema točkama smo lahko specializirani za algoritem DFS.
Topološko razvrščanje:
Uporablja se predvsem za razporejanje opravil iz danih odvisnosti med skupino opravil. V računalništvu se uporablja pri načrtovanju navodil, serializaciji podatkov, logični sintezi, določanju vrstnega reda nalog kompilacije.
Iskanje močno povezanih komponent grafa:
Uporabljal se je v grafu DFS, kadar je pot vsake oglišča v grafu do preostalih oglišč.
Reševanje ugank z eno samo rešitvijo:
Algoritem DFS je mogoče enostavno prilagoditi iskanju vseh rešitev v labirintu z vključitvijo vozlišč na obstoječo pot v obiskani niz.
KLJUČNE RAZLIKE:
- BFS najde najkrajšo pot do cilja, DFS pa na dno poddrevesa in nato nazaj.
- Celotna oblika BFS je iskanje po širini, medtem ko je celotna oblika DFS iskanje po globini.
- BFS uporablja čakalno vrsto za beleženje naslednje lokacije za obisk. ker DFS uporablja sklad za sledenje naslednje lokacije za obisk.
- BFS prečka glede na nivo drevesa, DFS pa po globini drevesa.
- BFS se izvaja s pomočjo seznama FIFO, na drugi strani pa DFS s pomočjo seznama LIFO.
- V BFS nikoli ne morete biti ujeti v končne zanke, medtem ko ste v DFS lahko ujeti v neskončne zanke.