Algoritmul de căutare Breadth First: Prezentare generală, importanță și aplicații

Graficele sunt peste tot în jurul nostru. Un grafic poate fi gândit ca o rețea interconectată de noduri și margini. Prietenii tăi de pe Facebook, conexiunile tale de pe LinkedIn sau urmăritorii tăi Twitter/Instagram constituie graficul tău social. În mod similar, dacă doriți să mergeți de la punctul A la punctul B, puteți face acest lucru prin mai multe rute, care pot fi vizualizate pe Google Maps.

Toate aceste opțiuni de traseu multiple de la punctul A la punctul B constituie, de asemenea, un grafic. Graficele sunt printre cele mai comune structuri de date pe care le întâlnim în mediul academic și în lumea reală deopotrivă, deoarece sunt atât de omniprezente. Și una dintre cele mai frecvente operații care pot fi efectuate pe un grafic este traversarea graficului.

Ce este Graph Traversal?

Graph Traversal este o metodă de a vizita fiecare nod dintr-un grafic exact o dată, cu viteză și precizie. Este un algoritm avansat de căutare a graficelor care vă permite să imprimați secvența nodurilor vizitate fără a fi prins într-o buclă infinită. Există mulți algoritmi de traversare a graficelor, cum ar fi Căutarea în profunzime , în primul rând în lățime , Algoritmul Djikstra, Algoritmul A -Star și multe altele.

Acest articol va analiza în profunzime Algoritmul de căutare Breadth First sau BFS.

Structura graficului

Înainte de a arunca o privire detaliată sub capota BFS, să ne familiarizăm cu unele terminologii ale graficului cu ajutorul graficului de mai sus:

Nodul rădăcină – Nodul în care începeți procesul de traversare. Pentru simplitate, putem considera A ca fiind nodul rădăcină.

Niveluri – Un nivel este o colecție de toate nodurile care sunt echidistante de nodul rădăcină. Deci, dacă considerăm nodul A ca fiind la Nivelul 0, nodurile B și C sunt la Nivelul 1, în timp ce nodurile D, E și F sunt la nivelul 2. O euristică simplă pentru determinarea numărului de nivel al unui nod este de a număra numărul de muchii dintre nodul menționat și nodul rădăcină. Rețineți că acest lucru funcționează numai dacă definiți nodul rădăcină să fie la nivelul 0.

Nodul părinte – Nodul părinte al unui nod este cel care se află la un nivel deasupra lui și adiacent acestuia. Poate fi considerat ca fiind nodul din care provine nodul respectiv. A este nodul părinte al lui B și C.

Noduri copil/copii – Noduri care se ramifică și sunt adiacente unui nod părinte. B și C sunt noduri copii ale lui A

Citiți: Top 10 tehnici de vizualizare a datelor

BFS este un algoritm de traversare a graficului pentru a explora eficient un arbore sau un grafic. Algoritmul începe cu un nod inițial (nodul rădăcină) și apoi continuă să exploreze toate nodurile adiacente acestuia, într-un mod pe lățimea întâi, spre deosebire de depth-first, care coboară o anumită ramură până la toate nodurile din acea ramură. sunt vizitate. Mai simplu spus, traversează graficul la nivel de nivel, fără a coborî un nivel până când toate nodurile din acel nivel sunt vizitate și marcate.

Funcționează pe principiul primul-intrat-primul-out (FIFO) și este implementat folosind o structură de date în coadă. Odată ce un nod este vizitat, acesta este inserat într-o coadă. Apoi este înregistrat și toate nodurile sale copii sunt introduse în coadă. Acest proces continuă până când toate nodurile din grafic sunt vizitate și înregistrate.

Să ne uităm la operațiunile detaliate de coadă pentru algoritmul BFS pentru graficul prezentat mai sus:

() – denotă coadă

[] – indică rezultatul tipărit

1. Introduceți A în coadă (a)
2. Tipăriți A, introduceți B și C în coadă (cb)[a]
3. Tipăriți B, introduceți nodurile sale secundare D și E în coadă (edc)[ba]
4. Tipăriți C, introduceți nodul său copil F în coadă (fed)[cba]
5. Tipăriți D, introduceți nodul său copil în coadă. Nu sunt. (fe)[dcba]
6. Tipăriți E, al cărui nod copil F a fost deja introdus în coadă. (f)[edcba]
7. Tipăriți F. [fedcba]

Ce face ca algoritmul BFS să fie important

Există o mulțime de motive pentru a implementa BFS ca metodă de căutare rapidă prin seturi de date vaste. Unele dintre caracteristicile importante care îl fac alegerea preferată pentru dezvoltatori și inginerii de date sunt:

• BFS poate explora eficient toate nodurile din grafic și poate găsi cea mai scurtă cale posibilă pentru a le explora pe toate.
• Numărul de iterații necesare pentru a parcurge întregul grafic este mai mic decât alți algoritmi de căutare.
• Deoarece este implementat folosind o coadă, arhitectura sa este robustă, fiabilă și elegantă.
• În comparație cu alți algoritmi, rezultatul BFS este exact și fără erori.
• Iterațiile BFS merg fără probleme, fără riscul de a fi prins într-o buclă infinită.

Checkout: Proiecte de vizualizare a datelor pe care le puteți replica

Aplicații ale algoritmului BFS

Datorită simplității și ușurinței sale de configurare, algoritmul BFS a găsit o utilizare pe scară largă în diferite situații cheie din lumea reală. Să ne uităm la câteva aplicații proeminente:

Crawlerele pentru motoarele de căutare – Încercați să vă imaginați o lume fără Google sau Bing. Nu poți. Motoarele de căutare sunt coloana vertebrală a internetului. Iar algoritmul BFS este coloana vertebrală a motoarelor de căutare. Este algoritmul principal utilizat pentru indexarea paginilor web. Algoritmul își începe călătoria de la pagina sursă (nodul rădăcină) și apoi urmează toate linkurile de pe pagina sursă într-o manieră pe lățime. Fiecare pagină web poate fi gândită ca un nod independent în grafic.

Traversari grafice neponderate – BFS poate identifica cea mai scurtă cale și arborele de acoperire minim într-un grafic neponderat. Găsirea celui mai scurt traseu înseamnă doar găsirea unei căi cu cel mai mic număr de muchii, pentru care BFS este ideal. Se poate termina munca vizitând cel mai mic număr de noduri.

Navigare GPS – BFS folosește sistemele GPS pentru a scoate la suprafață toate locațiile învecinate posibile de la punctul de plecare, ajutându-vă să navigați fără probleme de la punctul A la B.

Broadcasting – Broadcast networking folosește pachete ca unități pentru a transporta semnale și date. Algoritmul BFS conduce aceste pachete pentru a-și face drum spre toate nodurile din rețea la care ar trebui să ajungă.

Rețele P2P – Torrentele sau alte rețele de partajare de fișiere se bazează pe comunicarea P2P. BFS funcționează excelent pentru a găsi cele mai apropiate noduri, astfel încât transferul de date să poată avea loc mai rapid.

Citiți și: Beneficiile vizualizării datelor

Concluzie

Ergo, algoritmul de căutare Breadth First este unul dintre cei mai importanți algoritmi ai internetului modern. Sperăm că acest blog va servi drept un punct de plecare util în explorările algoritmilor de căutare.

Vă recomandăm să alegeți Diploma PG în Știința Datelor oferită de IIIT Bangalore găzduită pe upGrad, deoarece aici puteți obține întrebările dvs. 1-1 cu instructorii cursului. Nu se concentrează doar pe învățarea teoretică, ci acordă importanță cunoștințelor practice, care sunt esențiale pentru a pregăti cursanții pentru proiecte din lumea reală și pentru a vă oferi primul certificat NASSCOM din India, care vă ajută să obțineți locuri de muncă bine plătite în știința datelor.