Algoritmo de pesquisa em amplitude (BFS) com EXEMPLO
Sarah Chen
⚡ Resumo Inteligente
A Busca em Largura (BFS, do inglês Breadth First Search) é um algoritmo que percorre um grafo nível por nível, visitando todos os vizinhos de um nó antes de prosseguir para níveis mais profundos. Ela utiliza uma fila FIFO e encontra o caminho mais curto em grafos não ponderados, evitando loops infinitos.
O que é o algoritmo BFS (pesquisa em amplitude)?
A busca em largura (BFS, do inglês Breadth-first search) é um algoritmo usado para mapear dados em gráficos, pesquisar em árvores ou percorrer estruturas. A sigla BFS significa "busca em largura".
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
- Nos vários níveis dos dados, você pode marcar qualquer nó como o nó inicial para começar a busca. A busca em largura (BFS) visitará o nó, o marcará como visitado e o colocará na fila.
- Agora, a BFS visitará os nós mais próximos e os nós não visitados, marcando-os. Esses valores também são adicionados à fila. A fila opera na Modelo FIFO.
- De maneira semelhante, os nós mais próximos e não visitados restantes no grafo são analisados, marcados e adicionados à fila. Esses itens são removidos da fila à medida que são recebidos e impressos como resultado.
Por que precisamos do algoritmo BFS?
Existem inúmeras razões para utilizar o algoritmo BFS (Busca em Largura) para pesquisar em seu conjunto de dados. Alguns dos aspectos mais importantes que fazem deste algoritmo a 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, pode-se 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 de Busca em Largura (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 à fila BFS.
Passo 3)
Inicie a busca em largura (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 grafo que são adjacentes ao vértice V.
Passo 6)
Para cada vértice adjacente, digamos V1, caso ele ainda não tenha sido visitado, adicione V1 à fila BFS.
Passo 7)
O BFS visitará V1, marcará-lo-á como visitado e o excluirá da fila.
Exemplo de algoritmo BFS
Passo 1)
Você tem um gráfico com sete números que variam 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 nós adjacentes a 0 restantes e os nós não visitados 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 algumas regras importantes para usar o algoritmo BFS:
- Uma fila (FIFO – Primeiro a entrar, primeiro a sair) estrutura de dados é usado pelo BFS.
- Você marca qualquer nó no gráfico como raiz e começa a percorrer os dados a partir dele.
- A busca em largura (BFS) percorre todos os nós do grafo e continua removendo elementos.ping eles como 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 grafo 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 (Busca em Largura de Banda) pode facilmente criar o caminho mais curto e uma árvore geradora mínima para visitar todos os vértices do grafo no menor tempo possível e com alta precisão.
- Redes P2P: A busca em largura (BFS) pode ser implementada para localizar todos os nós mais próximos ou vizinhos em uma rede ponto a ponto. Isso permite 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.
