Algoritmul BFS (Broadth First Search) cu EXEMPLU

Ce este algoritmul BFS (Breadth-First Search)?

Breadth-first search (BFS) este un algoritm care este utilizat pentru a reprezenta grafice de date sau pentru a căuta în arbore sau pentru a traversa structuri. Forma completă a BFS este căutarea pe lățimea întâi.

Algoritmul vizitează și marchează eficient toate nodurile cheie într-un grafic într-un mod precis pe lățime. Acest algoritm selectează un singur nod (punct inițial sau sursă) într-un grafic și apoi vizitează toate nodurile adiacente nodului selectat. Amintiți-vă, BFS accesează aceste noduri unul câte unul.

Odată ce algoritmul vizitează și marchează nodul de pornire, apoi se deplasează către cele mai apropiate noduri nevizitate și le analizează. Odată vizitate, toate nodurile sunt marcate. Aceste iterații continuă până când toate nodurile graficului au fost vizitate și marcate cu succes.

Ce este Graph traversals?

O traversare a graficului este o metodologie utilizată în mod obișnuit pentru localizarea poziției vârfurilor în grafic. Este un algoritm avansat de căutare care poate analiza graficul cu viteză și precizie împreună cu marcarea secvenței vârfurilor vizitate. Acest proces vă permite să vizitați rapid fiecare nod dintr-un grafic fără a fi blocat într-o buclă infinită.

Arhitectura algoritmului BFS

În diferitele niveluri ale datelor, puteți marca orice nod ca nod de pornire sau inițial pentru a începe traversarea. BFS va vizita nodul și îl va marca ca vizitat și îl va plasa în coadă.
Acum BFS va vizita nodurile cele mai apropiate și nevizitate și le va marca. Aceste valori sunt, de asemenea, adăugate la coadă. Coada funcționează pe Model FIFO.
În mod similar, nodurile rămase cele mai apropiate și nevizitate din grafic sunt analizate marcate și adăugate la coadă. Aceste articole sunt șterse din coadă ca primire și tipărite ca rezultat.

De ce avem nevoie de algoritmul BFS?

Există numeroase motive pentru a utiliza algoritmul BFS pentru a-l folosi pentru căutarea setului de date. Unele dintre cele mai importante aspecte care fac din acest algoritm prima alegere sunt:

BFS este util pentru analiza nodurilor dintr-un grafic și pentru a construi calea cea mai scurtă de parcurgere prin acestea.
BFS poate parcurge un grafic în cel mai mic număr de iterații.
Arhitectura algoritmului BFS este simplă și robustă.
Rezultatul algoritmului BFS deține un nivel ridicat de precizie în comparație cu alți algoritmi.
Iterațiile BFS sunt fără întreruperi și nu există posibilitatea ca acest algoritm să fie prins într-o problemă de buclă infinită.

Cum funcționează algoritmul BFS?

Traversarea graficelor necesită algoritmului să viziteze, să verifice și/sau să actualizeze fiecare nod nevizitat într-o structură arborescentă. Traversările grafice sunt clasificate în ordinea în care vizitează nodurile din grafic.

Algoritmul BFS începe operația de la primul nod sau de pornire dintr-un grafic și îl parcurge complet. Odată ce traversează cu succes nodul inițial, atunci următorul vârf netraversat din grafic este vizitat și marcat.

Prin urmare, puteți spune că toate nodurile adiacente vârfului curent sunt vizitate și traversate în prima iterație. O metodologie simplă de coadă este utilizată pentru a implementa funcționarea unui algoritm BFS și constă din următorii pași:

Pas 1)

Fiecare vârf sau nod din grafic este cunoscut. De exemplu, puteți marca nodul ca V.

Pas 2)

În cazul în care vârful V nu este accesat, adăugați vârful V în coada BFS

Pas 3)

Începeți căutarea BFS și, după finalizare, marcați vârful V ca vizitat.

Pas 4)

Coada BFS nu este încă goală, prin urmare eliminați vârful V al graficului din coadă.

Pas 5)

Preluați toate vârfurile rămase pe grafic care sunt adiacente vârfului V

Pas 6)

Pentru fiecare vârf adiacent să spunem V1, în cazul în care nu este încă vizitat, adăugați V1 la coada BFS

Pas 7)

BFS va vizita V1 și îl va marca ca vizitat și îl va șterge din coadă.

Exemplu de algoritm BFS

Pas 1)

Aveți un grafic cu șapte numere cuprinse între 0 și 6.

Pas 2)

0 sau zero a fost marcat ca nod rădăcină.

Pas 3)

0 este vizitat, marcat și inserat în structura de date a cozii.

Pas 4)

Cele 0 noduri adiacente și nevizitate rămase sunt vizitate, marcate și inserate în coadă.

Pas 5)

Iterațiile de traversare sunt repetate până când toate nodurile sunt vizitate.

Regulile algoritmului BFS

Iată reguli importante pentru utilizarea algoritmului BFS:

O coadă (FIFO-First in First Out) structură de date este folosit de BFS.
Marcați orice nod din grafic ca rădăcină și începeți să traversați datele din acesta.
BFS parcurge toate nodurile din grafic și continuă să le arunce ca fiind finalizate.
BFS vizitează un nod adiacent nevizitat, îl marchează ca finalizat și îl inserează într-o coadă.
Îndepărtează vârful anterior din coadă în cazul în care nu se găsește un vârf adiacent.
Algoritmul BFS iterează până când toate vârfurile din grafic sunt parcurse cu succes și marcate ca finalizate.
Nu există bucle cauzate de BFS în timpul parcurgerii datelor de la orice nod.

Aplicații ale algoritmului BFS

Să aruncăm o privire la unele dintre aplicațiile din viața reală în care o implementare a algoritmului BFS poate fi foarte eficientă.

Grafice neponderate: Algoritmul BFS poate crea cu ușurință cea mai scurtă cale și un arbore de acoperire minim pentru a vizita toate vârfurile graficului în cel mai scurt timp posibil, cu o precizie ridicată.
Rețele P2P: BFS poate fi implementat pentru a localiza toate nodurile cele mai apropiate sau învecinate într-o rețea peer to peer. Aceasta va găsi mai rapid datele necesare.
Crawlerele web: Motoarele de căutare sau crawlerele web pot construi cu ușurință mai multe niveluri de indici prin utilizarea BFS. Implementarea BFS începe de la sursă, care este pagina web, apoi vizitează toate linkurile din acea sursă.
Sisteme de navigație: BFS vă poate ajuta să găsiți toate locațiile învecinate din locația principală sau sursă.
Difuzare în rețea: Un pachet difuzat este ghidat de algoritmul BFS pentru a găsi și ajunge la toate nodurile pentru care are adresa.

Rezumat

O traversare a graficului este un proces unic care necesită algoritmului să viziteze, să verifice și/sau să actualizeze fiecare nod nevizitat într-o structură arborescentă. Algoritmul BFS funcționează pe un principiu similar.
Algoritmul este util pentru analiza nodurilor dintr-un grafic și pentru a construi calea cea mai scurtă de parcurgere prin acestea.
Algoritmul străbate graficul în cel mai mic număr de iterații și în cel mai scurt timp posibil.
BFS selectează un singur nod (punct inițial sau sursă) într-un grafic și apoi vizitează toate nodurile adiacente nodului selectat. BFS accesează aceste noduri unul câte unul.
Datele vizitate și marcate sunt plasate într-o coadă de către BFS. O coadă funcționează pe primul intrat, primul ieșit. Prin urmare, elementul plasat mai întâi în grafic este șters primul și imprimat ca rezultat.
Algoritmul BFS nu poate fi niciodată prins într-o buclă infinită.
Datorită preciziei ridicate și implementării robuste, BFS este utilizat în mai multe soluții reale, cum ar fi rețele P2P, crawlerele web și difuzarea în rețea.