Uvod v algoritem BFS
Za učinkovit dostop do podatkov in njihovo upravljanje jih je mogoče shraniti in organizirati v posebni obliki, znani kot struktura podatkov. Obstaja veliko struktur podatkov, kot so sklad, niz, povezan seznam, čakalne vrste, drevesa in grafi, itd. V linearnih podatkovnih strukturah, kot so sklad, niz, povezani seznam in čakalna vrsta, so podatki organizirani v linearnem vrstnem redu, medtem ko v ne linearne strukture podatkov, kot so drevesa in grafi, so podatki organizirani hierarhično, ne v zaporedju. Graf je nelinearna podatkovna struktura, ki ima vozlišča in robove. Vozlišča v grafikonu lahko imenujemo tudi točki, ki so končne po številu, robovi pa so povezovalni črti med dvema vozliščema.
V zgornjem grafu so lahko točki predstavljeni kot V = (A, B, C, D, E), robovi pa so lahko definirani kot
E = (AB, AC, CD, BE)
Kaj je algoritem BFS?
Na splošno obstajata dva algoritma, ki se uporabljata za premikanje grafa. Gre za algoritme BFS (prvo iskanje širine) in algoritme DFS (globinsko prvo iskanje). Prehod grafikona je obiskan natanko enkrat v vsaki točki ali vozlišču in robu, v dobro določenem vrstnem redu. Prav tako je zelo pomembno spremljati obiskane točke, da se isto točko ne premika dvakrat. V algoritmu Breath First Search se iskanje začne od izbranega vozlišča ali izvornega vozlišča, prečkanje pa se nadaljuje skozi vozlišča, ki so neposredno povezana z izvornim vozliščem. Preprosteje povedano, v algoritmu BFS je treba najprej vodoravno premikati in prečkati trenutno plast, po kateri je treba premakniti na naslednjo plast.
Kako deluje algoritem BFS?
Vzemimo primer spodnjega grafa.
Pomembna naloga je najti najkrajšo pot v grafu med prečkanjem vozlišč. Ko prečkamo graf, prehaja iz neraziskanega stanja v odkrito in nazadnje postane popolnoma odkrito. Treba je opozoriti, da se je mogoče obtikati v nekem trenutku, medtem ko se skozi graf in vozlišče lahko obiščete dvakrat. Torej lahko uporabimo metodo označevanja vozlišč, potem ko spremeni stanje neodkritega do popolnega odkritja.
Na spodnji sliki lahko vidimo, da lahko vozlišča označimo na grafih, ko jih popolnoma odkrijemo, če jih označimo s črno. Začnemo lahko pri izvornem vozlišču in ko se prehod giblje skozi vsako vozlišče, jih lahko označimo, da jih prepoznamo.
Prehod se začne od vrha in nato potuje do odhodnih robov. Ko rob preide v neodkrito točko, je označen kot odkrit. Ko pa rob preide v povsem odkrito ali odkrito točko, se ne upošteva.
Pri usmerjenem grafu je vsak rob obiskan enkrat, pri usmerjenem grafu pa dvakrat, tj. Enkrat med obiskom vsakega vozlišča. Za uporabljeni algoritem se odloči na podlagi shranjevanja odkritih tock. V algoritmu BFS se čakalna vrsta uporablja tam, kjer se najprej odkrije najstarejša točka, nato pa se razprostira po plasteh iz začetne točke.
Koraki se izvajajo za algoritem BFS
Spodnji koraki se izvedejo za algoritem BFS.
- V danem grafu začnimo z vrhom, tj. V zgornjem diagramu je to vozlišče 0. Raven, v kateri je to točko prisotno, lahko označimo kot Layer 0.
- Naslednji korak je poiskati vse ostale točke, ki mejijo na začetno točko, tj. Vozlišče 0 ali so takoj dostopne od njega. Nato lahko označimo, da so ta sosednja točka prisotna v 1. sloju.
- Do zanke je mogoče priti zaradi zanke v grafu. Torej bi morali potovati samo do tistih tock, ki bi morale biti prisotne v isti plasti.
- Nato je označeno nadrejeno točko trenutnega toka, v katerem smo. Enako je treba opraviti za vse točke na 1. nivoju.
- Nato je naslednji korak, da najdemo vse točke, ki so en sam rob od vseh tock, ki so na nivoju 1. Ta novi niz vertiksov bo v 2. sloju.
- Zgornji postopek se ponavlja, dokler niso prečkana vsa vozlišča.
Primer:
Vzemimo primer spodnjega grafa in razumemo, kako deluje algoritem BFS. Na splošno se v algoritmu BFS uporablja čakalna vrsta za vstavljanje čakalnih vrst vozlišč pri prečkanju vozlišč.
V zgornjem grafu je treba najprej obiskati vozlišče 0 in to vozlišče se vklopi v spodnjo čakalno vrsto:
Po obisku vozlišča 0 so sosednja vozlišča 0, 1 in 2 na vrsti. Čakalna vrsta je lahko predstavljena kot spodaj: 
Potem bo obisk prvo vozlišče v čakalni vrsti, ki je 2. Po obisku vozlišča 2 je čakalna vrsta lahko predstavljena kot spodaj:
Po obisku vozlišča 2 se bo 5 postavilo v vrsto in ker za vozlišče 5 ni neobiskanih sosednjih vozlišč, je kljub temu 5 v vrsti, vendar ga ne bo obiskal dvakrat.
Nato je prvo vozlišče v čakalni vrsti 1, ki ga bomo obiskali. Sosednja vozlišča 3 in 4 sta v vrsti. Čakalna vrsta je predstavljena kot spodaj
Nato je prvo vozlišče v čakalni vrsti 5 in za to vozlišče ni več neobiskanih sosednjih vozlišč. Enako velja za vozlišča 3 in 4, za katera ni več neobiskanih sosednjih vozlišč.
Tako so prečkana vsa vozlišča in na koncu postane čakalna vrsta prazna.
Zaključek
Algoritem iskanja širine je priporočljiv za nekatere velike prednosti. Ena od številnih aplikacij algoritma BFS je izračunati najkrajšo pot. Uporablja se tudi pri mreženju za iskanje sosednjih vozlišč in jih najdemo na spletnih straneh družbenih omrežij, omrežnem oddajanju in odvozu smeti. Uporabniki morajo razumeti zahteve in vzorec podatkov, da jih lahko uporabijo za boljše delovanje.
Priporočeni članki
To je vodnik po algoritmu BFS. Tukaj razpravljamo o konceptu, delu, korakih in primeru uspešnosti v Algoritmu BFS. Če želite izvedeti več, lahko preberete tudi druge naše predlagane članke -
- Kaj je pohlepni algoritem?
- Algoritem sledenja Rayu
- Algoritem digitalnega podpisa
- Kaj je hibernacija Java?
- Kriptografija digitalnega podpisa
- BFS VS DFS | Najboljših 6 razlik z infografiko