Algoritam prve pretrage u širinu (BFS) s PRIMJEROM

Što je BFS algoritam (Breadth-First Search)?

Pretraživanje u širinu (BFS) je algoritam koji se koristi za grafički prikaz podataka ili pretraživanje stabla ili obilazak struktura. Puni oblik BFS-a je pretraživanje u širinu.

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 grafu i zatim posjećuje sve čvorove koji su susjedni odabranom čvoru. Zapamtite, BFS pristupa tim čvorovima jedan po jedan.

Nakon što algoritam posjeti i označi početni čvor, tada se kreće prema najbližim neposjećenim čvorovima i analizira ih. Nakon posjeta, svi čvorovi su označeni. Te se iteracije nastavljaju sve dok se svi čvorovi grafa uspješno ne posjete i obilježe.

Što je Graph traversals?

Obilazak grafa često je korištena metodologija za lociranje položaja vrhova u grafu. To je napredni algoritam pretraživanja koji može analizirati graf brzinom i preciznošću uz označavanje slijeda posjećenih vrhova. Ovaj proces vam omogućuje da brzo posjetite svaki čvor u grafikonu bez zaključavanja u beskonačnoj petlji.

Arhitektura BFS algoritma

1. Na različitim razinama podataka možete označiti bilo koji čvor kao početni ili inicijalni čvor za početak prolaska. BFS će posjetiti čvor, označiti ga kao posjećenog i staviti ga u red čekanja.
2. Sada će BFS posjetiti najbliže i neposjećene čvorove i označiti ih. Ove vrijednosti se također dodaju u red čekanja. Red čekanja radi na FIFO model.
3. Na sličan način, preostali najbliži i neposjećeni čvorovi na grafu se analiziraju, označavaju i dodaju u red. Te se stavke brišu iz reda kako se primaju i ispisuju kao rezultat.

Zašto nam je potreban BFS algoritam?

Postoje brojni razlozi za korištenje BFS algoritma za pretraživanje 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 grafu i konstruiranje najkraćeg puta kroz njih.
• BFS može proći kroz graf u najmanjem broju ponavljanja.
• Arhitektura BFS algoritma je jednostavna i robusna.
• Rezultat BFS algoritma ima visoku razinu točnosti u usporedbi s drugim algoritmima.
• BFS iteracije su besprijekorne i ne postoji mogućnost da ovaj algoritam bude uhvaćen u problem beskonačne petlje.

Kako radi BFS algoritam?

Obilaženje grafa zahtijeva da algoritam posjeti, provjeri i/ili ažurira svaki pojedini neposjećeni čvor u strukturi nalik stablu. Obilasci grafa 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 ga prelazi. Nakon što uspješno prijeđe početni čvor, posjećuje se i označava sljedeći nepređeni vrh na grafu.

Dakle, možete reći da su svi čvorovi susjedni trenutnom vrhu posjećeni i prošli kroz njih u prvoj iteraciji. Za implementaciju rada BFS algoritma koristi se jednostavna metodologija čekanja u redu, a sastoji se od sljedećih koraka:

Korak 1)

Svaki vrh ili čvor u grafu je poznat. Na primjer, možete označiti čvor kao V.

Korak 2)

U slučaju da se ne pristupa vrhu V, tada se vrh V dodaje u BFS red čekanja.

Korak 3)

Započnite BFS pretragu i nakon završetka označite vrh V kao posjećen.

Korak 4)

BFS red još uvijek nije prazan, stoga uklonite vrh V grafa 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, dodaje se V1 u BFS red.

Korak 7)

BFS će posjetiti V1, označiti ga kao posjećenog i izbrisati ga iz reda čekanja.

Primjer BFS algoritma

Korak 1)

Imate graf od sedam brojeva u rasponu od 0 do 6.

Korak 2)

0 ili nula je označen kao korijenski čvor.

Korak 3)

0 se posjećuje, označava i umeće u podatkovnu strukturu reda.

Korak 4)

Preostali 0-susjedni i neposjećeni čvorovi se posjećuju, označavaju i ubacuju u red.

Korak 5)

Iteracije obilaska se ponavljaju dok se ne posjete svi čvorovi.

Pravila BFS algoritma

Evo važnih pravila za korištenje BFS algoritma:

• Red (FIFO – Prvi unutra, Prvi van) struktura podataka koristi ga BFS.
• Označite bilo koji čvor u grafu kao korijen i od njega počnete pregledavati podatke.
• BFS prolazi kroz sve čvorove u grafu i zadržava ispuštene podatke.ping ih kao dovršene.
• BFS posjećuje susjedni neposjećeni čvor, označava ga kao gotovog i umeće u red čekanja.
• Uklanja prethodni vrh iz reda čekanja u slučaju da nije pronađen susjedni vrh.
• BFS algoritam iterira sve dok se svi vrhovi u grafu uspješno ne prođu i označe kao dovršeni.
• Nema petlji uzrokovanih BFS-om tijekom prelaska podataka iz bilo kojeg čvora.

Primjene BFS algoritma

Pogledajmo neke od stvarnih aplikacija u kojima implementacija BFS algoritma može biti vrlo učinkovita.

• Neponderirani grafikoni: BFS algoritam može lako stvoriti najkraći put i minimalno razapinjuće stablo kako bi se posjetili svi vrhovi grafa u najkraćem mogućem vremenu s visokom točnošću.
• P2P mreže: BFS se može implementirati za lociranje svih najbližih ili susjednih čvorova u peer-to-peer mreži. To će brže pronaći potrebne podatke.
• Web indeksi: Tražilice ili alati za indeksiranje mogu jednostavno izgraditi više razina indeksa koristeći BFS. Implementacija BFS-a počinje od izvora, a to je web stranica, a zatim posjećuje sve poveznice s tog izvora.
• Navigacijski sustavi: BFS može pomoći pronaći sve susjedne lokacije s glavne ili izvorne lokacije.
• Mrežno emitiranje: Emitirani paket je vođen BFS algoritmom da pronađe i dosegne sve čvorove za koje ima adresu.

Pitanja i odgovori