Što je BFS algoritam (pretraživanje u širini)?
Pretraživanje u širinu (BFS) algoritam je koji se koristi za grafički prikaz podataka ili pretraživanje stabla ili obilaženje struktura. Cjeloviti oblik BFS-a je pretraga koja je prva širina.
Algoritam učinkovito posjećuje i označava sve ključne čvorove u grafikonu na precizan način. Ovaj algoritam odabire jedan čvor (početnu ili izvornu točku) u grafikonu, a zatim posjećuje sve čvorove susjedne odabranom čvoru. Zapamtite, BFS pristupa tim čvorovima jedan po jedan.
Jednom kada algoritam posjeti i označi početni čvor, tada se kreće prema najbližim ne posjećenim čvorovima i analizira ih. Jednom posjećeni svi čvorovi su označeni. Te se ponavljanja nastavljaju sve dok svi čvorovi grafikona nisu uspješno posjećeni i označeni.
U ovom vodiču iz algoritma naučit ćete:
- Što je BFS algoritam (pretraživanje u širini)?
- Što su grafičke obilaznice?
- Arhitektura BFS algoritma
- Zašto nam treba BFS algoritam?
- Kako funkcionira BFS algoritam?
- Primjer BFS algoritma
- Pravila BFS algoritma
- Primjene BFS algoritma
Što su grafičke obilaznice?
Obilazanje grafa uobičajena je metodologija za lociranje položaja temena na grafu. To je napredni algoritam pretraživanja koji može analizirati graf brzinom i preciznošću zajedno s označavanjem slijeda posjećenih vrhova. Ovaj vam postupak omogućuje brzi posjet svakom čvoru na grafu bez zatvaranja u beskonačnu petlju.
Arhitektura BFS algoritma
- Na različitim razinama podataka možete bilo koji čvor označiti kao početni ili početni čvor za započinjanje prelaska. BFS će posjetiti čvor i označiti ga kao posjećeni te ga smjestiti u red čekanja.
- Sada će BFS posjetiti najbliže i ne posjećene čvorove i označiti ih. Te se vrijednosti također dodaju u red čekanja. Red čekanja radi po modelu FIFO.
- Na sličan način analiziraju se označeni i dodani u red preostali najbliži i ne posjećeni čvorovi na grafikonu. Te se stavke brišu iz reda primanja i ispisuju kao rezultat.
Zašto nam treba BFS algoritam?
Brojni su razlozi da se BFS algoritam koristi kao traženje vašeg skupa podataka. Neki od najvažnijih aspekata koji ovaj algoritam čine vašim prvim izborom su:
- BFS je koristan za analizu čvorova u grafikonu i konstrukciju najkraćeg puta prelaska kroz njih.
- BFS može prelaziti graf u najmanjem broju iteracija.
- Arhitektura BFS algoritma je jednostavna i robusna.
- Rezultat BFS algoritma ima visoku razinu preciznosti u usporedbi s drugim algoritmima.
- BFS iteracije su besprijekorne i ne postoji mogućnost da se ovaj algoritam uhvati u problem s beskonačnom petljom.
Kako funkcionira BFS algoritam?
Okretanje grafa zahtijeva da algoritam posjeti, provjeri i / ili ažurira svaki pojedini ne posjećeni čvor u strukturi nalik stablu. Prelazi grafova kategorizirani su prema redoslijedu kojim posjećuju čvorove na grafu.
BFS algoritam započinje operaciju od prvog ili početnog čvora u grafu i temeljito je prelazi. Jednom kada uspješno pređe početni čvor, tada se posjećuje i označava sljedeći neprevučeni vrh na grafikonu.
Stoga možete reći da su svi čvorovi susjedni trenutnom tjemenu posjećeni i pređeni u prvoj iteraciji. Za implementaciju rada BFS algoritma koristi se jednostavna metodologija reda, koja se sastoji od sljedećih koraka:
Korak 1)
Svaki vrh ili čvor na grafu je poznat. Na primjer, čvor možete označiti kao V.
Korak 2)
U slučaju da se vrhu V ne pristupi, dodajte vrh V u BFS Red
Korak 3)
Pokrenite BFS pretraživanje, a nakon završetka označite vrh V kao posjećen.
Korak 4)
BFS red još uvijek nije prazan, stoga uklonite vrh V grafikona iz reda.
Korak 5)
Dohvatite sve preostale vrhove na grafu koji su susjedni vrhu V
Korak 6)
Za svaki susjedni vrh recimo V1, u slučaju da još nije posjećen, dodajte V1 u BFS red
Korak 7)
BFS će posjetiti V1 i označiti ga kao posjetili te ga izbrisati iz reda čekanja.
Primjer BFS algoritma
Korak 1)
Imate grafikon od sedam brojeva u rasponu od 0 - 6.
Korak 2)
0 ili nula označena je kao korijenski čvor.
Korak 3)
0 je posjećeno, označeno i umetnuto u strukturu podataka o redu čekanja.
Korak 4)
Preostalih 0 susjednih i ne posjećenih čvorova posjećuju se, označavaju i ubacuju u red čekanja.
Korak 5)
Iteracije prelaska ponavljaju se dok se ne posjete svi čvorovi.
Pravila BFS algoritma
Evo važnih pravila za upotrebu BFS algoritma:
- BFS koristi strukturu podataka o redu čekanja (FIFO-prvi u prvom izlazu).
- Bilo koji čvor na grafikonu označite kao korijen i započnite s njime prelaziti podatke.
- BFS prelazi sve čvorove na grafikonu i nastavlja ih ispuštati kao dovršene.
- BFS posjećuje susjedni neposjećeni čvor, označava ga kao gotov i ubacuje u red čekanja.
- Uklanja prethodni vrh iz reda u slučaju da nije pronađen susjedni vrh.
- BFS algoritam ponavlja se sve dok svi vrhovi na grafikonu ne budu uspješno pređeni i označeni kao dovršeni.
- Ne postoje petlje uzrokovane BFS-om tijekom prelaska podataka s bilo kojeg čvora.
Primjene BFS algoritma
Pogledajmo neke stvarne aplikacije u kojima implementacija BFS algoritma može biti vrlo učinkovita.
- Neponderirani grafovi: BFS algoritam može lako stvoriti najkraći put i minimalno rasponično stablo za posjećivanje svih vrhova grafa u najkraćem mogućem roku s velikom preciznošću.
- P2P mreže: BFS se može implementirati za lociranje svih najbližih ili susjednih čvorova u peer to peer mreži. Tako ćete brže pronaći potrebne podatke.
- Web alati za indeksiranje : tražilice ili alati za indeksiranje weba mogu jednostavno izgraditi više razina indeksa koristeći BFS. Implementacija BFS-a započinje od izvora, a to je web stranica, a zatim posjećuje sve veze s tog izvora.
- Navigacijski sustavi: BFS može pomoći u pronalaženju svih susjednih lokacija s glavnog ili izvornog mjesta.
- Mrežno emitiranje: Emitirani paket vođen je BFS algoritmom kako bi pronašao i došao do svih čvorova kojima ima adresu.
Sažetak
- Okretanje grafa jedinstveni je postupak koji zahtijeva da algoritam posjeti, provjeri i / ili ažurira svaki pojedini ne posjećeni čvor u strukturi nalik stablu. BFS algoritam radi na sličnom principu.
- Algoritam je koristan za analizu čvorova u grafu i konstrukciju najkraćeg puta prelaska kroz njih.
- Algoritam prolazi graf u najmanjem broju iteracija i u najkraćem mogućem vremenu.
- BFS odabire jedan čvor (početnu ili izvornu točku) na grafikonu, a zatim posjećuje sve čvorove susjedne odabranom čvoru. BFS pristupa tim čvorovima jedan po jedan.
- Posjećeni i označeni podaci BFS stavlja u red čekanja. Red čekanja funkcionira prvo na prvom do prvog izlaza. Stoga se element koji se prvo postavi u grafikon prvo briše i kao rezultat ispisuje.
- BFS algoritam nikada ne može biti uhvaćen u beskonačnu petlju.
- Zahvaljujući visokoj preciznosti i robusnoj implementaciji, BFS se koristi u više stvarnih rješenja poput P2P mreža, web alata za indeksiranje i mrežnog emitiranja.