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.

Uma vez que o algoritmo visita e marca o nó inicial, ele se move em direção ao nearest nós não visitados 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

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á o nearest e nós não visitados e os marca. Esses valores também são adicionados à fila. A fila funciona no Modelo FIFO.
  3. De maneira semelhante, o restante nearesOs nós t 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 no seguintewing passos:

Passo 1)

Funcionamento do Algoritmo BFS

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

Passo 2)

Funcionamento do Algoritmo BFS

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

Passo 3)

Funcionamento do Algoritmo BFS

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

Passo 4)

Funcionamento do Algoritmo BFS

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

Passo 5)

Funcionamento do Algoritmo BFS

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

Passo 6)

Funcionamento do Algoritmo BFS

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

Passo 7)

Funcionamento do Algoritmo BFS

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

Exemplo de algoritmo BFS

Passo 1)

Exemplo de algoritmo BFS

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

Passo 2)

Exemplo de algoritmo BFS

0 ou zero foi marcado como um nó raiz.

Passo 3)

Exemplo de algoritmo BFS

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

Passo 4)

Exemplo de algoritmo BFS

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

Passo 5)

Exemplo de algoritmo BFS

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 nearest ou nós 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.