Introducere în algoritmul BFS
Pentru a accesa și gestiona eficient datele, acestea pot fi stocate și organizate într-un format special cunoscut sub numele de structura de date. Există multe structuri de date, cum ar fi Stack, Array, Listă legată, Cozi, arbori și grafice etc. Structuri de date liniare precum Arbori și Grafice, datele sunt organizate ierarhic nu într-o secvență. Graficul este o structură de date neliniare, care are noduri și muchii. Nodurile din grafic pot fi, de asemenea, denumite vârfuri care sunt în număr finit, iar marginile sunt liniile de conectare între oricare două noduri.
În graficul de mai sus, vârfurile pot fi reprezentate ca V = (A, B, C, D, E), iar marginile pot fi definite ca
E = (AB, AC, CD, BE)
Ce este algoritmul BFS?
În general, există doi algoritmi care sunt folosiți pentru traversarea unui grafic. Sunt algoritmi BFS (Breadth-First Search) și DFS (Depth First Search). Traversalul graficului vizitează exact o dată fiecare vertex sau nod și margine, într-o ordine bine definită. De asemenea, este foarte important să urmăriți vârfurile vizitate, astfel încât același vertex să nu fie traversat de două ori. În algoritmul Breath First Search, traversarea pornește de la un nod sau nod sursă selectat și traversarea continuă prin nodurile conectate direct la nodul sursă. În termeni mai simpli, în algoritmul BFS, ar trebui să se miște mai întâi orizontal și să traverseze stratul curent, după care a trecut la următorul strat.
Cum funcționează algoritmul BFS?
Să luăm exemplul graficului de mai jos.
Sarcina importantă este să găsiți cea mai scurtă cale dintr-un grafic în timp ce parcurgeți nodurile. Când traversăm un grafic, vertexul trece de la starea nedescoperită la starea descoperită și în cele din urmă devine complet descoperit. Trebuie menționat că este posibil să vă blocați la un moment dat în timp ce parcurgeți un grafic și un nod poate fi vizitat de două ori. Deci putem folosi o metodă de marcare a nodurilor după ce schimbă starea de a nu fi descoperit în a fi descoperit complet.
În imaginea de mai jos putem vedea că nodurile pot fi marcate în grafice, deoarece devin complet descoperite marcându-le cu negru. Putem începe de la nodul sursă și pe măsură ce traversarea progresează prin fiecare nod, ele pot fi marcate pentru a fi identificate.
Traversarea pornește de la un vertex și apoi călătorește spre marginile de ieșire. Atunci când o muchie se îndreaptă către un vertex nedescoperit, este marcat ca fiind descoperit. Dar când o margine se îndreaptă către un vertex complet descoperit sau descoperit, acesta este ignorat.
Pentru un grafic direcționat, fiecare muchie este vizitată o singură dată și pentru un grafic nedirectat, acesta este vizitat de două ori adică o dată în timp ce vizitați fiecare nod. Algoritmul care va fi utilizat este decis pe baza modului în care sunt stocate vârfurile descoperite. În algoritmul BFS, coada este folosită acolo unde este descoperit primul vertex cel mai vechi și apoi se propagă prin straturile din vertexul de pornire.
Etapele sunt efectuate pentru un algoritm BFS
Etapele de mai jos sunt efectuate pentru un algoritm BFS.
- Într-un grafic dat, să pornim de la un vertex, adică în diagrama de mai sus este nodul 0. Nivelul, în care este prezent acest vertex, poate fi notat ca strat 0.
- Următorul pas este de a găsi toate celelalte vârfuri care sunt adiacente vertexului de pornire, adică nodul 0 sau imediat accesibile de la acesta. Atunci putem marca aceste vârfuri adiacente pentru a fi prezente la stratul 1.
- Este posibil să veniți pe același vertex datorită unei bucle din grafic. Deci, ar trebui să călătorim doar către acele vârfuri care ar trebui să fie prezente în același strat.
- În continuare, este marcat vertexul părinte al vertexului curent la care ne aflăm. Același lucru trebuie efectuat pentru toate vârfurile de la nivelul 1.
- Apoi, următorul pas este să găsiți toate acele vertice care sunt la o singură margine distanță de toate vârfurile care se află la nivelul 1. Acest nou set de vârfuri va fi la nivelul 2.
- Procesul de mai sus se repetă până când sunt traversate toate nodurile.
Exemplu:
Să luăm exemplul graficului de mai jos și să înțelegem cum funcționează algoritmul BFS. În general, într-un algoritm BFS, o coadă este folosită pentru a pune în coadă nodurile în timp ce traversați nodurile.
În graficul de mai sus, mai întâi trebuie vizitat nodul 0 și acest nod este înscris în coada de mai jos:
După vizitarea nodului 0, nodul vecin de la 0, 1 și 2 sunt înscriși în coadă. Coada poate fi reprezentată după cum urmează: 
Apoi va fi vizitat primul nod din coada care este 2. După vizitarea nodului 2, coada poate fi reprezentată ca mai jos:
După vizitarea nodului 2, 5 va fi în coadă și întrucât nu există noduri vecine nevizitate pentru nodul 5, totuși 5 este în coadă, dar nu va fi vizitat de două ori.
În continuare, primul nod din coadă este 1 care va fi vizitat. Nodurile vecine 3 și 4 sunt plasate în coadă. Coada este reprezentată ca mai jos
În continuare, primul nod din coadă este 5, iar pentru acest nod, nu mai există noduri vecine nevizitate. Același lucru este valabil și pentru nodurile 3 și 4 pentru care nu există mai multe noduri vecine nevăzute.
Deci toate nodurile sunt traversate și, în final, coada devine goală.
Concluzie
Algoritmul de căutare a lărgimii oferă câteva avantaje deosebite pentru a-l recomanda. Una dintre numeroasele aplicații ale algoritmului BFS este de a calcula calea cea mai scurtă. De asemenea, este utilizat în rețelele pentru a găsi noduri vecine și poate fi găsit în site-urile de rețea socială, în difuzarea rețelei și în colectarea gunoiului. Utilizatorii trebuie să înțeleagă cerința și modelul de date pentru a o utiliza pentru o performanță mai bună.
Articole recomandate
Acesta a fost un ghid pentru algoritmul BFS. Aici discutăm conceptul, modul de lucru, etapele și exemplul performanței în algoritmul BFS. De asemenea, puteți parcurge și celelalte articole sugerate pentru a afla mai multe -
- Ce este un algoritm lacom?
- Algoritmul de urmărire a razei
- Algoritmul semnăturii digitale
- Ce este Java Hibernate?
- Criptografie cu semnătură digitală
- BFS VS DFS | Top 6 Diferențe cu Infografie