Algoritmo Breadth First Search (BFS)

Cos’è l’algoritmo BFS (Breadth-First Search)?

Breadth-first search (BFS) è un algoritmo che viene utilizzato per rappresentare graficamente i dati o cercare l’albero o attraversare le strutture. La forma completa di BFS è la ricerca Breadth-first.

L’algoritmo visita e contrassegna in modo efficiente tutti i nodi chiave in un grafico in modo accurato in termini di ampiezza. Questo algoritmo seleziona un singolo nodo (punto iniziale o di origine) in un grafico e quindi visita tutti i nodi adiacenti al nodo selezionato. Ricorda, BFS accede a questi nodi uno per uno.

Una volta che l’algoritmo visita e segna il nodo di partenza, si sposta verso i nodi non visitati più vicini e li analizza. Una volta visitati, tutti i nodi sono contrassegnati. Queste iterazioni continuano fino a quando tutti i nodi del grafico non sono stati visitati e contrassegnati correttamente.

Che cos’è Graph traversals?

Un attraversamento del grafo è una metodologia comunemente usata per localizzare la posizione del vertice nel grafico. È un algoritmo di ricerca avanzato in grado di analizzare il grafico con velocità e precisione insieme a segnare la sequenza dei vertici visitati. Questo processo consente di visitare rapidamente ogni nodo in un grafico senza essere bloccati in un ciclo infinito.

L’architettura dell’algoritmo BFS

1. Nei vari livelli dei dati, è possibile contrassegnare qualsiasi nodo come nodo iniziale o iniziale per iniziare l’attraversamento. Il BFS visiterà il nodo e lo contrassegnerà come visitato e lo metterà in coda.
2. Ora il BFS visiterà i nodi più vicini e non visitati e li contrassegnerà. Anche questi valori vengono aggiunti alla coda. La coda funziona sul modello FIFO.
3. In modo simile, i restanti nodi più vicini e non visitati sul grafico vengono analizzati contrassegnati e aggiunti alla coda. Questi elementi vengono eliminati dalla coda come ricezione e stampati come risultato.

Perché abbiamo bisogno dell’algoritmo BFS?

Esistono numerosi motivi per utilizzare l’algoritmo BFS da utilizzare come ricerca del set di dati. Alcuni degli aspetti più vitali che rendono questo algoritmo la tua prima scelta sono:

• BFS è utile per analizzare i nodi in un grafico e costruire il percorso più breve di attraversamento di questi.
• BFS can traverse through a graph in the smallest number of iterations.
• The architecture of the BFS algorithm is simple and robust.
• The result of the BFS algorithm holds a high level of accuracy in comparison to other algorithms.
• BFS iterations are seamless, and there is no possibility of this algorithm getting caught up in an infinite loop problem.

How does BFS Algorithm Work?

Graph traversal requires the algorithm to visit, check, and/or update every single un-visited node in a tree-like structure. Graph traversals are categorized by the order in which they visit the nodes on the graph.

BFS algorithm starts the operation from the first or starting node in a graph and traverses it thoroughly. Once it successfully traverses the initial node, then the next non-traversed vertex in the graph is visited and marked.

Hence, you can say that all the nodes adjacent to the current vertex are visited and traversed in the first iteration. A simple queue methodology is utilized to implement the working of a BFS algorithm, and it consists of the following steps:

Step 1)

Each vertex or node in the graph is known. For instance, you can mark the node as V.

Step 2)

In case the vertex V is not accessed then add the vertex V into the BFS Queue

Step 3)

Start the BFS search, and after completion, Mark vertex V as visited.

Step 4)

The BFS queue is still not empty, hence remove the vertex V of the graph from the queue.

Step 5)

Retrieve all the remaining vertices on the graph that are adjacent to the vertex V

Step 6)

For each adjacent vertex let’s say V1, in case it is not visited yet then add V1 to the BFS queue

Step 7)

BFS will visit V1 and mark it as visited and delete it from the queue.

Example BFS Algorithm

Step 1)

You have a graph of seven numbers ranging from 0 – 6.

Step 2)

0 or zero has been marked as a root node.

Step 3)

0 is visited, marked, and inserted into the queue data structure.

Step 4)

Remaining 0 adjacent and unvisited nodes are visited, marked, and inserted into the queue.

Step 5)

Traversing iterations are repeated until all nodes are visited.

Rules of BFS Algorithm

Here, are important rules for using BFS algorithm:

• A queue (FIFO-First in First Out) data structure is used by BFS.
• You mark any node in the graph as root and start traversing the data from it.
• BFS traverses all the nodes in the graph and keeps dropping them as completed.
• BFS visits an adjacent unvisited node, marks it as done, and inserts it into a queue.
• Removes the previous vertex from the queue in case no adjacent vertex is found.
• BFS algorithm iterates until all the vertices in the graph are successfully traversed and marked as completed.
• There are no loops caused by BFS during the traversing of data from any node.

Applications of BFS Algorithm

Let’s take a look at some of the real-life applications where a BFS algorithm implementation can be highly effective.

• Un-weighted Graphs: BFS algorithm can easily create the shortest path and a minimum spanning tree to visit all the vertices of the graph in the shortest time possible with high accuracy.
• P2P Networks: BFS can be implemented to locate all the nearest or neighboring nodes in a peer to peer network. This will find the required data faster.
• Web Crawlers: Search engines or web crawlers can easily build multiple levels of indexes by employing BFS. BFS implementation starts from the source, which is the web page, and then it visits all the links from that source.
• Navigation Systems: BFS can help find all the neighboring locations from the main or source location.
• Network Broadcasting: A broadcasted packet is guided by the BFS algorithm to find and reach all the nodes it has the address for.

Summary

• A graph traversal is a unique process that requires the algorithm to visit, check, and/or update every single un-visited node in a tree-like structure. BFS algorithm works on a similar principle.
• L’algoritmo è utile per analizzare i nodi in un grafico e costruire il percorso più breve di attraversamento di questi.
• L’algoritmo attraversa il grafico nel minor numero di iterazioni e nel più breve tempo possibile.
• BFS seleziona un singolo nodo (iniziale o punto sorgente) in un grafico e quindi visita tutti i nodi adiacenti al nodo selezionato. BFS accede a questi nodi uno per uno.
• I dati visitati e contrassegnati vengono inseriti in una coda da BFS. Una coda funziona su base first in first out. Quindi, l’elemento inserito per primo nel grafico viene eliminato per primo e stampato di conseguenza.
• L’algoritmo BFS non può mai rimanere intrappolato in un ciclo infinito.
• Grazie all’elevata precisione e all’implementazione robusta, BFS viene utilizzato in più soluzioni reali come reti P2P, Web Crawler e Network Broadcasting.

fonte: https://www.guru99.com/