O que que é Algoritmo BFS (Pesquisa em Largura)?
A Pesquisa em Largura (BFS) é um algoritmo usado para representar graficamente dados ou árvore de pesquisa ou estruturas de passagem. A forma completa do BFS é a pesquisa em amplitude.
O algoritmo visita e marca com eficiência todos os nós-chave em um gráfico de maneira precisa. Este algoritmo seleciona um único nó (ponto inicial ou fonte) em um gráfico e, em seguida, 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.
Neste tutorial de Algoritmo, você aprenderá:
- O que é Algoritmo BFS (Pesquisa em Largura)?
- O que são travessias do gráfico?
- A arquitetura do algoritmo BFS
- Por que precisamos do algoritmo BFS?
- Como funciona o algoritmo BFS?
- Exemplo de Algoritmo BFS
- Regras de Algoritmo BFS
- Aplicações de Algoritmo BFS
O que são travessias de gráfico?
A travessia de um 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. Este processo permite que você visite rapidamente cada nó em um gráfico sem ficar travado em um loop infinito.
A arquitetura do algoritmo BFS
- Nos vários níveis de dados, você pode marcar qualquer nó como o ponto inicial ou nó inicial para começar a atravessar. O BFS visitará o nó e o marcará como visitado e o colocará na fila.
- 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.
- 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 quando recebidos e impressos como resultado.
Por que precisamos do Algoritmo BFS?
Existem várias razões 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 atravessá-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 possui um alto nível de precisão em comparação com outros algoritmos.
- As iterações BFS são contínuas e não há possibilidade desse 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 do primeiro nó ou nó inicial em um gráfico e o percorre completamente. Uma vez que ele atravessa com sucesso o nó inicial, então o próximo vértice não atravessado no gráfico é visitado e marcado.
Portanto, você pode 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:
Etapa 1)
Cada vértice ou nó no gráfico é conhecido. Por exemplo, você pode marcar o nó como V.
Etapa 2)
Caso o vértice V não seja acessado, adicione o vértice V à fila BFS
Etapa 3)
Inicie a pesquisa BFS e, após a conclusão, marque o vértice V como visitado.
Etapa 4)
A fila BFS ainda está não está vazio, portanto, remova o vértice V do gráfico da fila.
Etapa 5)
Recupere todos os vértices restantes no gráfico adjacente ao vértice V
Etapa 6)
Para cada vértice adjacente, digamos V1, caso ainda não tenha sido visitado, adicione V1 à fila BFS
Etapa 7)
O BFS irá visitar a V1 e marcá-la como visitada e excluí-la da fila.
Exemplo de algoritmo BFS
Etapa 1)
Você tem um gráfico de sete números variando de 0 a 6.
Etapa 2)
0 ou zero foi marcado como um nó raiz.
Etapa 3)
0 é visitado, marcado e inserido na estrutura de dados da fila.
Etapa 4)
0 nós adjacentes e não visitados restantes são visitados, marcados e inseridos na fila.
Etapa 5)
As iterações de travessia 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:
- Estrutura de dados de uma fila (FIFO-First in First Out) é 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 no gráfico e continua descartando-os quando concluídos.
- O BFS visita um nó adjacente não visitado, marca-o como concluído e o insere em uma fila.
- Remove o vértice anterior da fila no caso de nenhum vértice adjacente ser encontrado.
- O algoritmo BFS itera até que todos os vértices no 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 veja alguns dos aplicativos da vida real onde uma implementação de algoritmo BFS pode ser altamente eficaz.
- Gráficos não ponderados: o algoritmo BFS pode facilmente criar o caminho mais curto e uma árvore de abrangência mínima para visitar todos os vértices do gráfico no menor tempo possível com alta precisão.
- Redes P2P: 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 construir facilmente vários níveis de índices empregando o 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 pela rede ing: Um pacote transmitido é guiado pelo algoritmo BFS para encontrar e alcançar todos os nós para os quais tem 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 um estrutura semelhante a uma árvore. O algoritmo BFS funciona em um princípio semelhante.
- O algoritmo é útil para analisar os nós em um gráfico e construir o caminho mais curto para atravessá-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, a seguir, 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 uma fila pelo BFS. Uma fila funciona de acordo com a ordem de chegada. Portanto, o elemento colocado no gráfico primeiro é excluído primeiro e impresso como resultado.
- O algoritmo BFS nunca pode ser pego em um loop infinito.
- Devido à alta precisão e implementação robusta, o BFS é usado em várias soluções da vida real como redes P2P, Web Crawlers, e transmissão pela rede.