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 crtanje podataka ili pretraživanje stabla ili prelaženje struktura. Potpuni 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

Archistruktura BFS algoritma

  1. U različitim razinama podataka, možete označiti bilo koji čvor kao početni ili početni čvor za početak obilaska. BFS će posjetiti čvor i označiti ga kao posjećenog te ga smjestiti u red čekanja.
  2. Sada će BFS posjetiti najbliže i neposjećene čvorove i označiti ih. Ove se vrijednosti 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 grafikonu analiziraju se označeni i dodaju u red čekanja. Ove stavke se brišu iz reda čekanja kao primanje 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 obiđeni u prvoj iteraciji. Jednostavna metodologija čekanja koristi se za implementaciju rada BFS algoritma, a sastoji se od sljedećih koraka:

Korak 1)

Rad BFS algoritma

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

Korak 2)

Rad BFS algoritma

U slučaju da se ne pristupi vrhu V, dodajte vrh V u BFS red

Korak 3)

Rad BFS algoritma

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

Korak 4)

Rad BFS algoritma

BFS red još uvijek nije prazan, stoga uklonite vrh V grafa iz reda.

Korak 5)

Rad BFS algoritma

Dohvatite sve preostale vrhove na grafu koji su susjedni vrhu V

Korak 6)

Rad BFS algoritma

Za svaki susjedni vrh, recimo V1, u slučaju da još nije posjećen, dodajte V1 u BFS red čekanja

Korak 7)

Rad BFS algoritma

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

Primjer BFS algoritma

Korak 1)

Primjer BFS algoritma

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

Korak 2)

Primjer BFS algoritma

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

Korak 3)

Primjer BFS algoritma

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

Korak 4)

Primjer BFS algoritma

Preostalih 0 susjednih i neposjećenih čvorova se posjećuju, označavaju i umeću u red čekanja.

Korak 5)

Primjer BFS algoritma

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

Pravila BFS algoritma

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

  • Red čekanja (FIFO-prvi ušao prvi izašao) struktura podataka koristi ga BFS.
  • Označite bilo koji čvor na grafikonu kao korijenski i počnete prelaziti podatke iz njega.
  • BFS prolazi kroz sve čvorove u grafu i nastavlja ih ispuštati 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 u slučaju da nije pronađen susjedni vrh.
  • BFS algoritam ponavlja sve dok se svi vrhovi u grafu uspješno ne prijeđu i označi 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 za posjet svim vrhovima 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. Tako ćete 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.

rezime

  • Prolazak grafa jedinstven je proces koji zahtijeva da algoritam posjeti, provjeri i/ili ažurira svaki pojedinačni neposjećeni čvor u strukturi nalik na stablo. BFS algoritam radi na sličnom principu.
  • Algoritam je koristan za analizu čvorova u grafu i konstruiranje najkraćeg puta kroz njih.
  • Algoritam prelazi graf u najmanjem broju iteracija i najkraćem mogućem vremenu.
  • BFS odabire jedan čvor (početnu ili izvornu točku) na grafikonu, a zatim posjećuje sve čvorove uz odabrani čvor. BFS pristupa tim čvorovima jedan po jedan.
  • Posjećene i označene podatke BFS stavlja u red čekanja. Red čekanja radi na principu prvi ušao prvi izašao. Dakle, element koji je prvi postavljen na graf se prvi briše i ispisuje kao rezultat.
  • BFS algoritam nikada ne može biti uhvaćen u beskonačnu petlju.
  • Zbog visoke preciznosti i robusne implementacije, BFS se koristi u više stvarnih rješenja kao što su P2P mreže, Web Crawleri i Network Broadcasting.