Algoritmo de pesquisa em amplitude (BFS) com EXEMPLO

O que é o algoritmo BFS (pesquisa em amplitude)?

A pesquisa em largura (BFS) é um algoritmo usado para representar graficamente dados ou pesquisar árvores ou atravessar estruturas. A forma completa do BFS é a pesquisa em amplitude.

O algoritmo visita e marca com eficiência todos os nós principais em um gráfico de maneira ampla e precisa. Este algoritmo seleciona um único nó (ponto inicial ou de origem) em um grafo e então visita todos os nós adjacentes ao nó selecionado. Lembre-se de que o BFS acessa esses nós um por um.

Depois que o algoritmo visita e marca o nó inicial, ele se move em direção aos nós não visitados mais próximos e os analisa. Uma vez visitados, todos os nós são marcados. Essas iterações continuam até que todos os nós do gráfico tenham sido visitados e marcados com sucesso.

O que são travessias de gráfico?

Uma travessia de gráfico é uma metodologia comumente usada para localizar a posição do vértice no gráfico. É um algoritmo de busca avançado que pode analisar o gráfico com rapidez e precisão além de marcar a sequência dos vértices visitados. Esse processo permite visitar rapidamente cada nó em um gráfico sem ficar preso em um loop infinito.

A arquitetura do algoritmo BFS

1. Nos vários níveis dos dados, você pode marcar qualquer nó como o nó inicial ou inicial para começar a percorrer. O BFS irá visitar o nó e marcá-lo como visitado e colocá-lo na fila.
2. Agora o BFS visitará os nós mais próximos e não visitados e os marcará. Esses valores também são adicionados à fila. A fila funciona no Modelo FIFO.
3. De maneira semelhante, os nós restantes mais próximos e não visitados no gráfico são analisados, marcados e adicionados à fila. Esses itens são excluídos da fila como recebimento e impressos como resultado.

Por que precisamos do algoritmo BFS?

Existem vários motivos para utilizar o algoritmo BFS para pesquisar seu conjunto de dados. Alguns dos aspectos mais vitais que tornam este algoritmo sua primeira escolha são:

• O BFS é útil para analisar os nós em um gráfico e construir o caminho mais curto para percorrê-los.
• O BFS pode percorrer um gráfico no menor número de iterações.
• A arquitetura do algoritmo BFS é simples e robusta.
• O resultado do algoritmo BFS mantém um alto nível de precisão em comparação com outros algoritmos.
• As iterações do BFS são perfeitas e não há possibilidade de esse algoritmo ser pego em um problema de loop infinito.

Como funciona o algoritmo BFS?

A travessia do gráfico requer que o algoritmo visite, verifique e/ou atualize cada nó não visitado em uma estrutura semelhante a uma árvore. As travessias do gráfico são categorizadas pela ordem em que visitam os nós do gráfico.

O algoritmo BFS inicia a operação a partir do primeiro nó ou nó inicial em um gráfico e o percorre completamente. Depois de atravessar com sucesso o nó inicial, o próximo vértice não percorrido no gráfico é visitado e marcado.

Portanto, podemos dizer que todos os nós adjacentes ao vértice atual são visitados e percorridos na primeira iteração. Uma metodologia de fila simples é utilizada para implementar o funcionamento de um algoritmo BFS e consiste nas seguintes etapas:

Passo 1)

Cada vértice ou nó do gráfico é conhecido. Por exemplo, você pode marcar o nó como V.

Passo 2)

Caso o vértice V não seja acessado, adicione o vértice V à fila BFS

Passo 3)

Inicie a pesquisa BFS e, após a conclusão, marque o vértice V como visitado.

Passo 4)

A fila BFS ainda não está vazia, portanto, remova o vértice V do gráfico da fila.

Passo 5)

Recupere todos os vértices restantes no gráfico que são adjacentes ao vértice V

Passo 6)

Para cada vértice adjacente digamos V1, caso ainda não tenha sido visitado adicione V1 à fila BFS

Passo 7)

O BFS irá visitar V1 e marcá-lo como visitado e excluí-lo da fila.

Exemplo de algoritmo BFS

Passo 1)

Você tem um gráfico de sete números variando de 0 a 6.

Passo 2)

0 ou zero foi marcado como um nó raiz.

Passo 3)

0 é visitado, marcado e inserido na estrutura de dados da fila.

Passo 4)

Os 0 nós adjacentes e não visitados restantes são visitados, marcados e inseridos na fila.

Passo 5)

As iterações de passagem são repetidas até que todos os nós sejam visitados.

Regras do Algoritmo BFS

Aqui estão regras importantes para usar o algoritmo BFS:

• Uma fila (FIFO-First in First Out) estrutura de dados é usado pelo BFS.
• Você marca qualquer nó no gráfico como raiz e começa a percorrer os dados dele.
• O BFS percorre todos os nós do gráfico e continua descartando-os quando concluídos.
• O BFS visita um nó adjacente não visitado, marca-o como concluído e insere-o em uma fila.
• Remove o vértice anterior da fila caso nenhum vértice adjacente seja encontrado.
• O algoritmo BFS itera até que todos os vértices do gráfico sejam percorridos com sucesso e marcados como concluídos.
• Não há loops causados ​​pelo BFS durante a passagem de dados de qualquer nó.

Aplicações do Algoritmo BFS

Vamos dar uma olhada em algumas das aplicações da vida real onde a implementação de um algoritmo BFS pode ser altamente eficaz.

• Gráficos não ponderados: O algoritmo BFS pode facilmente criar o caminho mais curto e uma árvore geradora mínima para visitar todos os vértices do gráfico no menor tempo possível com alta precisão.
• Redes P2P: O BFS pode ser implementado para localizar todos os nós mais próximos ou vizinhos em uma rede ponto a ponto. Isso encontrará os dados necessários mais rapidamente.
• Rastreadores da Web: Mecanismos de pesquisa ou rastreadores da web podem criar facilmente vários níveis de índices empregando BFS. A implementação do BFS começa na fonte, que é a página da web, e então visita todos os links dessa fonte.
• Sistemas de navegação: O BFS pode ajudar a encontrar todos os locais vizinhos do local principal ou de origem.
• Transmissão em rede: Um pacote transmitido é guiado pelo algoritmo BFS para encontrar e alcançar todos os nós para os quais possui o endereço.

Resumo

• Uma travessia de gráfico é um processo único que requer que o algoritmo visite, verifique e/ou atualize cada nó não visitado em uma estrutura semelhante a uma árvore. O algoritmo BFS funciona com um princípio semelhante.
• O algoritmo é útil para analisar os nós em um gráfico e construir o caminho mais curto para percorrê-los.
• O algoritmo percorre o gráfico no menor número de iterações e no menor tempo possível.
• O BFS seleciona um único nó (ponto inicial ou de origem) em um gráfico e então visita todos os nós adjacentes ao nó selecionado. O BFS acessa esses nós um por um.
• Os dados visitados e marcados são colocados em fila pelo BFS. Uma fila funciona primeiro a entrar, primeiro a sair. Conseqüentemente, o elemento colocado primeiro no gráfico é excluído primeiro e impresso como resultado.
• O algoritmo BFS nunca pode ficar preso em um loop infinito.
• Devido à alta precisão e implementação robusta, o BFS é usado em múltiplas soluções da vida real, como redes P2P, Web Crawlers e Network Broadcasting.