Kaj je algoritem BFS (iskanje najprej v širini)?
Iskanje po širini (BFS) je algoritem, ki se uporablja za grafikovanje podatkov ali iskanje drevesa ali prehajanje struktur. Celotna oblika BFS je iskanje po širini.
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. Ne pozabite, da BFS dostopa do teh vozlišč enega za drugim.
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.
V tej vadnici Algoritma boste izvedeli:
- Kaj je algoritem BFS (iskanje najprej v širini)?
- Kaj je graf prečkanje?
- Arhitektura algoritma BFS
- Zakaj potrebujemo algoritem BFS?
- Kako deluje algoritem BFS?
- Primer algoritma BFS
- Pravila algoritma BFS
- Uporaba algoritma BFS
Kaj je graf prečkanje?
Prehod grafa je pogosto uporabljena metodologija za določanje položaja oglišča v grafu. Gre za napredni algoritem iskanja, ki lahko analizira graf hitro in natančno ter označi zaporedje obiskanih točk. Ta postopek vam omogoča hiter obisk vsakega vozlišča v grafu, ne da bi bil zaklenjen v neskončno zanko.
Arhitektura algoritma BFS
- Na različnih ravneh podatkov lahko katero koli vozlišče označite kot začetno ali začetno vozlišče za začetek prečkanja. BFS bo vozlišče obiskal, označil kot obiskano in ga postavil v čakalno vrsto.
- Zdaj bo BFS obiskal najbližja in neobiskana vozlišča ter jih označil. Te vrednosti so dodane tudi v čakalno vrsto. Čakalna vrsta deluje po modelu FIFO.
- Na podoben način se analizirajo preostala najbližja in neobiskana vozlišča na grafu, označena in dodana v čakalno vrsto. Ti elementi so izbrisani iz čakalne vrste kot prejeti in kot rezultat natisnjeni.
Zakaj potrebujemo algoritem BFS?
Obstaja veliko razlogov za uporabo algoritma BFS, ki ga lahko uporabite za iskanje vašega nabora podatkov. Nekateri najpomembnejši vidiki, zaradi katerih je ta algoritem vaša prva izbira, so:
- BFS je koristen za analizo vozlišč v grafu in konstruiranje najkrajše poti prehoda skozi ta.
- BFS lahko prečka graf v najmanjšem številu ponovitev.
- Arhitektura algoritma BFS je preprosta in robustna.
- Rezultat algoritma BFS ima visoko stopnjo natančnosti v primerjavi z drugimi algoritmi.
- Ponovitve BFS so brezhibne in ni možnosti, da bi se ta algoritem ujel v problem neskončne zanke.
Kako deluje algoritem BFS?
Prehod grafa zahteva, da algoritem obišče, preveri in / ali posodobi vsako posamezno neobiskano vozlišče v drevesni strukturi. Prehodi grafov so razvrščeni po vrstnem redu obiska vozlišč na grafu.
BFS algoritem začne operacijo od prvega ali začetnega vozlišča v grafu in ga temeljito prečka. Ko uspešno prečka začetno vozlišče, se obišče in označi naslednje neprehodno oglišče na grafu.
Zato lahko rečete, da so vsa vozlišča, ki mejijo na trenutno točko, obiskana in prevožena v prvi ponovitvi. Za izvajanje algoritma BFS se uporablja preprosta metodologija čakalnih vrst, sestavljena iz naslednjih korakov:
Korak 1)
Vsaka točka ali vozlišče v grafu je znano. Na primer, vozlišče lahko označite kot V.
2. korak)
V primeru, da točka V ni dostopna, dodajte točko V v čakalno vrsto BFS
3. korak)
Zaženite iskanje BFS in po zaključku označite točko V kot obiskano.
4. korak)
Čakalna vrsta BFS še vedno ni prazna, zato odstranite točko V grafa iz čakalne vrste.
5. korak)
Pridobite vse preostale točke na grafu, ki mejijo na točko V
6. korak)
Za vsako sosednjo točko recimo V1, če še ni obiskano, dodajte V1 v čakalno vrsto BFS
7. korak)
BFS bo obiskal V1, ga označil kot obiskanega in ga izbrisal iz čakalne vrste.
Primer algoritma 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.
Pravila algoritma BFS
Tu so pomembna pravila za uporabo algoritma BFS:
- BFS uporablja podatkovno strukturo čakalne vrste (FIFO - prvi v prvem izhodu).
- Vsako vozlišče v grafu označite kot korensko in začnete prečkati podatke iz njega.
- BFS prečka vsa vozlišča v grafu in jih po zaključku nenehno spušča.
- BFS obišče sosednje neobisnjeno vozlišče, ga označi kot končano in ga vstavi v čakalno vrsto.
- Odstrani prejšnjo točko iz čakalne vrste, če ne najde nobene sosednje točke.
- Algoritem BFS se ponavlja, dokler niso vse točke na grafu uspešno prehodne in označene kot dokončane.
- Med prehodom podatkov iz katerega koli vozlišča BFS ne povzroča zank.
Uporaba algoritma BFS
Oglejmo si nekaj resničnih aplikacij, kjer je lahko implementacija algoritma BFS zelo učinkovita.
- Netehtani grafi: BFS algoritem lahko enostavno ustvari najkrajšo pot in minimalno drevo, da v najkrajšem možnem času z visoko natančnostjo obišče vse točke grafa.
- P2P omrežja: BFS je mogoče implementirati, da poišče vsa najbližja ali sosednja vozlišča v enakovrednem omrežju. 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.
- Navigacijski sistemi: BFS vam lahko pomaga najti vse sosednje lokacije z glavne ali izvorne lokacije.
- Omrežno oddajanje: Oddani paket vodi algoritem BFS, da najde in doseže vsa vozlišča, na katera ima naslov.
Povzetek
- Prehod grafa je edinstven postopek, ki zahteva, da algoritem obišče, preveri in / ali posodobi vsako posamezno neobiskano vozlišče v drevesni strukturi. BFS algoritem deluje po podobnem principu.
- Algoritem je uporaben za analizo vozlišč v grafu in konstruiranje najkrajše poti prehoda skozi ta.
- Algoritem prečka graf v najmanjšem številu ponovitev in v najkrajšem možnem času.
- BFS 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. BFS dostopa do teh vozlišč enega za drugim.
- Obiskane in označene podatke BFS postavi v čakalno vrsto. Čakalna vrsta deluje od prvega do prvega. Zato se element, ki je najprej vgrajen v graf, najprej izbriše in posledično natisne.
- Algoritem BFS se nikoli ne more ujeti v neskončno zanko.
- Zaradi visoke natančnosti in robustne izvedbe se BFS uporablja v več resničnih rešitvah, kot so omrežja P2P, spletni pajki in omrežno oddajanje.