Algoritmo di ricerca in ampiezza: panoramica, importanza e applicazioni

I grafici sono tutti intorno a noi. Un grafo può essere pensato come una rete interconnessa di nodi e bordi. I tuoi amici su Facebook, le tue connessioni su LinkedIn o i tuoi follower su Twitter/Instagram costituiscono il tuo grafico sociale. Allo stesso modo, se vuoi andare dal punto A al punto B, puoi farlo attraverso più percorsi, visualizzabili su Google Maps.

Tutte queste molteplici opzioni di percorso dal punto A al punto B costituiscono anche un grafico. I grafici sono tra le strutture di dati più comuni che incontriamo nel mondo accademico e nel mondo reale allo stesso modo perché sono così onnipresenti. E una delle operazioni più frequenti che possono essere eseguite su un grafico è l'attraversamento del grafico.

Che cos'è Graph Traversal?

Graph Traversal è un metodo per visitare ogni nodo in un grafico esattamente una volta con velocità e precisione. Si tratta di un algoritmo di ricerca grafico avanzato che consente di stampare la sequenza dei nodi visitati senza rimanere intrappolati in un ciclo infinito. Esistono molti algoritmi di attraversamento del grafico come Depth-First Search , Width -First Search , Djikstra's Algorithm , A-Star Algorithm e altro ancora.

Questo articolo approfondirà l' algoritmo di ricerca in ampiezza o BFS.

Struttura del grafico

Prima di dare uno sguardo dettagliato sotto il cofano di BFS, familiarizziamo con alcune terminologie dei grafici con l'aiuto del grafico sopra:

Nodo radice : il nodo in cui si avvia il processo di attraversamento. Per semplicità, possiamo considerare A come il nodo radice.

Livelli : un livello è una raccolta di tutti i nodi equidistanti dal nodo radice. Quindi, se consideriamo il nodo A al livello 0, i nodi B e C sono al livello 1, mentre i nodi D, E ed F sono al livello 2. Una semplice euristica per determinare il numero di livello di un nodo è contare il numero di spigoli tra detto nodo e il nodo radice. Si noti che questo funziona solo se si definisce il nodo radice al livello 0.

Nodo principale: il nodo principale di un nodo è quello che si trova un livello sopra di esso e adiacente ad esso. Può essere pensato come il nodo da cui ha origine detto nodo. A è il nodo padre di B e C.

Nodi figlio/figli – Nodi che si diramano e sono adiacenti a un nodo padre. B e C sono nodi figli di A

Leggi: Le 10 migliori tecniche di visualizzazione dei dati

BFS è un algoritmo di attraversamento di grafi per esplorare un albero o un grafo in modo efficiente. L'algoritmo inizia con un nodo iniziale (nodo radice) e quindi procede ad esplorare tutti i nodi adiacenti ad esso, in modo breadth-first, invece di depth-first, che scende lungo un particolare ramo fino a tutti i nodi in quel ramo sono visitati. In parole povere, attraversa il grafico a livello di livello, non scendendo di un livello finché tutti i nodi in quel livello non vengono visitati e contrassegnati.

Funziona secondo il principio FIFO (first-in-first-out) ed è implementato utilizzando una struttura di dati di coda. Una volta che un nodo viene visitato, viene inserito in una coda. Quindi viene registrato e tutti i suoi nodi figli vengono inseriti nella coda. Questo processo continua finché tutti i nodi nel grafico non vengono visitati e registrati.

Diamo un'occhiata alle operazioni di coda dettagliate per l'algoritmo BFS per il grafico sopra riportato:

() – indica la coda

[] – indica l'output stampato

1. Inserisci A nella coda (a)
2. Stampa A, inserisci B e C nella coda (cb)[a]
3. Stampa B, inserisci i suoi nodi figli D ed E nella coda (edc)[ba]
4. Stampa C, inserisci il suo nodo figlio F in coda (fed)[cba]
5. Stampa D, inserisci il suo nodo figlio nella coda. Non ce ne sono. (fe)[dcba]
6. Stampa E, il cui nodo figlio F è già stato inserito nella coda. (f)[edcba]
7. Stampa F. [fedcba]

Cosa rende importante l'algoritmo BFS

Ci sono una miriade di ragioni per implementare BFS come metodo per cercare rapidamente in vasti set di dati. Alcune delle caratteristiche salienti che lo rendono la scelta preferita per sviluppatori e data engineer sono:

• BFS può esplorare efficacemente tutti i nodi nel grafico e scoprire il percorso più breve possibile per esplorarli tutti.
• Il numero di iterazioni necessarie per attraversare l'intero grafo è inferiore rispetto ad altri algoritmi di ricerca.
• Poiché è implementato utilizzando una coda, la sua architettura è robusta, affidabile ed elegante.
• Rispetto ad altri algoritmi, l'output di BFS è esatto e privo di errori.
• Le iterazioni BFS procedono senza intoppi, senza correre il rischio di rimanere intrappolati in un ciclo infinito.

Checkout: progetti di visualizzazione dei dati che puoi replicare

Applicazioni dell'algoritmo BFS

Grazie alla sua semplicità e facilità di configurazione, l'algoritmo BFS ha trovato un uso diffuso in varie situazioni chiave del mondo reale. Diamo un'occhiata ad alcune applicazioni importanti:

Crawler dei motori di ricerca : prova a immaginare un mondo senza Google o Bing. Non puoi. I motori di ricerca sono la spina dorsale di Internet. E l'algoritmo BFS è la spina dorsale dei motori di ricerca. È l'algoritmo principale utilizzato per indicizzare le pagine Web. L'algoritmo inizia il suo viaggio dalla pagina di origine (nodo radice) e quindi segue tutti i collegamenti su quella pagina di origine in modo ampio. Ogni pagina web può essere considerata come un nodo indipendente nel grafico.

Traversali di grafici non ponderati : BFS è in grado di identificare il percorso più breve e l'albero di copertura minimo in un grafico non ponderato. Trovare il percorso più breve significa semplicemente trovare un percorso con il minor numero di bordi, per il quale BFS è l'ideale. Può lavorare visitando il minor numero di nodi.

Navigazione GPS – BFS sfrutta i sistemi GPS per far emergere tutte le possibili località vicine dal punto di partenza, aiutandoti a navigare dal punto A al punto B senza interruzioni.

Trasmissione : la rete di trasmissione utilizza i pacchetti come unità per trasportare segnali e dati. L'algoritmo BFS guida questi pacchetti per raggiungere tutti i nodi della rete che dovrebbero raggiungere.

Reti P2P : i torrent o altre reti di condivisione file si basano sulla comunicazione P2P. BFS funziona in modo eccellente per trovare i nodi più vicini in modo che il trasferimento dei dati possa avvenire più velocemente.

Leggi anche: Vantaggi della visualizzazione dei dati

Conclusione

Ergo, l' algoritmo di ricerca in ampiezza è uno degli algoritmi più importanti di Internet moderno. Si spera che questo blog serva come un pratico punto di partenza nelle esplorazioni dell'algoritmo di ricerca.

Ti consigliamo di scegliere PG Diploma in Data Science offerto da IIIT Bangalore ospitato su upGrad perché qui puoi ottenere le tue domande 1-1 con gli istruttori del corso. Non si concentra solo sull'apprendimento teorico, ma dà importanza alla conoscenza pratica, che è essenziale per preparare gli studenti ad affrontare progetti del mondo reale e fornirti il ​​​​1° certificato NASSCOM dell'India, che ti aiuta a ottenere lavori ben pagati in Data Science.