O que é BFS?

A pesquisa em largura (BFS) é baseada na passagem de nós, adicionando os vizinhos de cada nó à fila de passagem começando no nó raiz. O BFS de um gráfico é semelhante ao de uma árvore, com a exceção de que os gráficos podem ter ciclos. Em contraste com a busca em profundidade, todos os nós vizinhos em uma determinada profundidade são investigados antes de prosseguir para o próximo nível.

Algoritmo BFS

A seguir estão as etapas envolvidas no emprego da pesquisa ampla para explorar um gráfico:

1. Pegue os dados para a matriz ou lista de adjacências do gráfico.
2. Crie uma fila e preencha-a com itens.
3. Ative o nó raiz (ou seja, obtenha o nó raiz no início da fila).
4. Retire o cabeçalho da fila (ou elemento inicial) e, em seguida, enfileire todos os nós próximos da fila, da esquerda para a direita. Simplesmente retire o cabeçalho da fila e retome a operação se um nó não tiver nós próximos que precisem ser investigados. (Observação: se surgir um vizinho que já foi investigado ou está na fila, não o coloque na fila; em vez disso, ignore-o.)
5. Continue desta maneira até que a fila esteja vazia.

Aplicativos BFS

Devido à flexibilidade do algoritmo, a pesquisa em amplitude é bastante útil no mundo real. Estes são alguns deles:

1. Em uma rede ponto a ponto, nós pares são descobertos. A maioria dos clientes de torrent, como BitTorrent, uTorrent e qBittorent, emprega esse processo para encontrar “sementes” e “pares” na rede.
2. O índice é construído usando técnicas de travessia de gráfico em rastreamento da web. O procedimento começa com a página de origem como nó raiz e desce até todas as páginas secundárias vinculadas à página de origem (e esse processo continua). Devido à profundidade reduzida da árvore de recursão, a pesquisa em amplitude tem uma vantagem inerente aqui.
3. O uso de sistemas de navegação GPS usando o GPS permite realizar uma pesquisa ampla para localizar locais próximos.
4. A técnica de Cheney, que emprega o conceito de busca em largura, é usada para coletar lixo.

Exemplo de travessia BFS

Para começar, vejamos um exemplo simples. Começaremos com 0 como o nó raiz e avançaremos no gráfico.

Passo 1: Enfileirar(0)

Fila

Passo 2: Desenfileirar(0), Enfileirar(1), Enfileirar(3), Enfileirar(4)

Fila

Etapa 3: Desenfileirar(1), Enfileirar(2)

Fila

Passo 4: Desenfileirar(3), Enfileirar(5). Não adicionaremos 1 à fila novamente porque 0 já foi explorado.

Fila

Etapa 5: Desenfileirar(4)

Fila

Etapa 6: Desenfileirar(2)

Fila

Etapa 7: Desenfileirar(5)

Fila

A fila está vazia agora, então interromperemos o processo.

Programa Java de pesquisa ampla

Existem várias abordagens para lidar com o código. Discutiremos principalmente as etapas envolvidas na implementação de uma pesquisa ampla em Java. Uma lista de adjacências ou uma matriz de adjacências pode ser usada para armazenar gráficos; qualquer um dos métodos é aceitável. A lista de adjacências será usada para representar nosso gráfico em nosso código. Ao implementar o algoritmo de pesquisa em largura em Java, é muito mais fácil lidar com a lista de adjacência, pois só precisamos percorrer a lista de nós anexados a cada nó, uma vez que o nó é retirado da fila do início (ou início) do nó. fila.

O gráfico utilizado para demonstrar o código será idêntico ao utilizado no exemplo anterior.

BFSTraversal.java

 import java.io.*; import java.util.*; public class BFSTraversal { private int node; /* total number number of nodes in the graph */ private LinkedList adj[]; /* adjacency list */ private Queue que; /* maintaining a queue */ BFSTraversal(int v) { node = v; adj = new LinkedList[node]; 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[node]; 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(6); graph.insertedge(0, 1); 3); 4); graph.insertedge(4, 5); graph.insertedge(3, graph.insertedge(1, 2); 0); graph.insertedge(2, graph.insertedge(5, system.out.println('breadth first traversal is:'); graph.bfs(0); pre> <p> <strong>Output:</strong> </p> <pre> Breadth First Traversal for the graph is: 0 1 3 4 2 5 </pre> <hr></v;>