Neste artigo, discutiremos o algoritmo BFS na estrutura de dados. A pesquisa em largura é um algoritmo de passagem de gráfico que começa a percorrer o gráfico a partir do nó raiz e explora todos os nós vizinhos. Em seguida, seleciona o nó mais próximo e explora todos os nós inexplorados. Ao usar BFS para travessia, qualquer nó no gráfico pode ser considerado como o nó raiz.

Existem muitas maneiras de percorrer o gráfico, mas entre elas, o BFS é a abordagem mais comumente usada. É um algoritmo recursivo para pesquisar todos os vértices de uma estrutura de dados em árvore ou gráfico. O BFS coloca cada vértice do gráfico em duas categorias – visitado e não visitado. Ele seleciona um único nó em um grafo e, em seguida, visita todos os nós adjacentes ao nó selecionado.

Aplicações do algoritmo BFS

As aplicações do algoritmo de largura são dadas a seguir -

• O BFS pode ser usado para encontrar locais vizinhos de um determinado local de origem.
• Em uma rede ponto a ponto, o algoritmo BFS pode ser usado como um método transversal para encontrar todos os nós vizinhos. A maioria dos clientes de torrent, como BitTorrent, uTorrent, etc., emprega esse processo para encontrar 'sementes' e 'peers' na rede.
• O BFS pode ser usado em rastreadores da web para criar índices de páginas da web. É um dos principais algoritmos que podem ser usados ​​para indexar páginas da web. Ele começa a percorrer a partir da página de origem e segue os links associados à página. Aqui, cada página da web é considerada um nó no gráfico.
• O BFS é usado para determinar o caminho mais curto e a árvore geradora mínima.
• O BFS também é usado na técnica de Cheney para duplicar a coleta de lixo.
• Pode ser usado no método Ford-Fulkerson para calcular o fluxo máximo em uma rede de fluxo.

Algoritmo

As etapas envolvidas no algoritmo BFS para explorar um gráfico são fornecidas a seguir -

Passo 1: SET STATUS = 1 (estado pronto) para cada nó em G

finalizar a compra com git

Passo 2: Enfileirar o nó inicial A e definir seu STATUS = 2 (estado de espera)

Etapa 3: Repita as etapas 4 e 5 até que QUEUE esteja vazio

Passo 4: Retire da fila um nó N. Processe-o e defina seu STATUS = 3 (estado processado).

Etapa 5: Enfileirar todos os vizinhos de N que estão no estado pronto (cujo STATUS = 1) e definir

data java agora

seu ESTADO = 2

(estado de espera)

[FIM DO LOOP]

Etapa 6: SAÍDA

Exemplo de algoritmo BFS

Agora, vamos entender o funcionamento do algoritmo BFS usando um exemplo. No exemplo abaixo, há um gráfico direcionado com 7 vértices.

No gráfico acima, o caminho mínimo 'P' pode ser encontrado usando o BFS que começará no Nó A e terminará no Nó E. O algoritmo usa duas filas, nomeadamente QUEUE1 e QUEUE2. QUEUE1 contém todos os nós que serão processados, enquanto QUEUE2 contém todos os nós que são processados ​​e excluídos da QUEUE1.

Agora, vamos começar a examinar o gráfico começando no Nó A.

comando no nó js

Passo 1 - Primeiro, adicione A à fila1 e NULL à fila2.

 QUEUE1 = {A} QUEUE2 = {NULL} 

Passo 2 - Agora, exclua o nó A da fila1 e adicione-o à fila2. Insira todos os vizinhos do nó A na fila1.

 QUEUE1 = {B, D} QUEUE2 = {A} 

etapa 3 - Agora, exclua o nó B da fila1 e adicione-o à fila2. Insira todos os vizinhos do nó B na fila1.

 QUEUE1 = {D, C, F} QUEUE2 = {A, B} 

Passo 4 - Agora, exclua o nó D da fila1 e adicione-o à fila2. Insira todos os vizinhos do nó D na fila1. O único vizinho do Nó D é F, pois já está inserido, portanto não será inserido novamente.

 QUEUE1 = {C, F} QUEUE2 = {A, B, D} 

Etapa 5 - Exclua o nó C da fila1 e adicione-o à fila2. Insira todos os vizinhos do nó C na fila1.

 QUEUE1 = {F, E, G} QUEUE2 = {A, B, D, C} 

Etapa 5 - Exclua o nó F da fila1 e adicione-o à fila2. Insira todos os vizinhos do nó F na fila1. Como todos os vizinhos do nó F já estão presentes, não iremos inseri-los novamente.

exemplo de lista em java

 QUEUE1 = {E, G} QUEUE2 = {A, B, D, C, F} 

Etapa 6 - Exclua o nó E da fila1. Como todos os seus vizinhos já foram adicionados, não iremos inseri-los novamente. Agora, todos os nós são visitados e o nó de destino E é encontrado na fila2.

 QUEUE1 = {G} QUEUE2 = {A, B, D, C, F, E} 

Complexidade do algoritmo BFS

A complexidade de tempo do BFS depende da estrutura de dados usada para representar o gráfico. A complexidade de tempo do algoritmo BFS é O(V+E) , já que no pior caso, o algoritmo BFS explora cada nó e aresta. Em um gráfico, o número de vértices é O(V), enquanto o número de arestas é O(E).

A complexidade espacial do BFS pode ser expressa como O(V) , onde V é o número de vértices.

Implementação do algoritmo BFS

Agora, vamos ver a implementação do algoritmo BFS em java.

Neste código, estamos usando a lista de adjacências para representar nosso gráfico. A implementação do algoritmo de pesquisa em amplitude em Java torna muito mais fácil lidar com a lista de adjacências, uma vez que só precisamos percorrer a lista de nós anexados a cada nó depois que o nó for retirado da fila do início (ou início) da fila.

Neste exemplo, o gráfico que estamos usando para demonstrar o código é fornecido da seguinte forma -

 import java.io.*; import java.util.*; public class BFSTraversal { private int vertex; /* total number number of vertices in the graph */ private LinkedList adj[]; /* adjacency list */ private Queue que; /* maintaining a queue */ BFSTraversal(int v) { vertex = v; adj = new LinkedList[vertex]; for (int i=0; i<v; i++) { adj[i]="new" linkedlist(); } que="new" void insertedge(int v,int w) adj[v].add(w); * adding an edge to the adjacency list (edges are bidirectional in this example) bfs(int n) boolean nodes[]="new" boolean[vertex]; initialize array for holding data int a="0;" nodes[n]="true;" que.add(n); root node is added top of queue while (que.size() !="0)" n="que.poll();" remove element system.out.print(n+' '); print (int i="0;" < adj[n].size(); iterate through linked and push all neighbors into if (!nodes[a]) only insert nodes they have not been explored already nodes[a]="true;" que.add(a); public static main(string args[]) bfstraversal graph="new" bfstraversal(10); graph.insertedge(0, 1); 2); 3); graph.insertedge(1, graph.insertedge(2, 4); graph.insertedge(3, 5); 6); graph.insertedge(4, 7); graph.insertedge(5, graph.insertedge(6, graph.insertedge(7, 8); system.out.println('breadth first traversal is:'); graph.bfs(2); pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/64/bfs-algorithm-3.webp" alt="Breadth First Search Algorithm"> <h3>Conclusion</h3> <p>In this article, we have discussed the Breadth-first search technique along with its example, complexity, and implementation in java programming language. Here, we have also seen the real-life applications of BFS that show it the important data structure algorithm.</p> <p>So, that&apos;s all about the article. Hope, it will be helpful and informative to you.</p> <hr></v;>