Introdução ao algoritmo BFS
Para acessar e gerenciar os dados com eficiência, eles podem ser armazenados e organizados em um formato especial conhecido como estrutura de dados. Existem muitas estruturas de dados, como Pilha, Matriz, Lista vinculada, Filas, Árvores e Gráficos etc. Em estruturas de dados lineares, como Pilha, Matriz, Lista vinculada e Fila, os dados são organizados em ordem linear, enquanto que, em estruturas de dados lineares como árvores e gráficos, os dados são organizados hierarquicamente e não em uma sequência. O gráfico é uma estrutura de dados não linear que possui nós e arestas. Os nós no gráfico também podem ser chamados de vértices em número finito e as arestas são as linhas de conexão entre dois nós.
No gráfico acima, os vértices podem ser representados como V = (A, B, C, D, E) e as arestas podem ser definidas como
E = (AB, AC, CD, BE)
Qual é o algoritmo BFS?
Geralmente existem dois algoritmos que são usados para percorrer um gráfico. Eles são os algoritmos BFS (pesquisa da primeira largura) e DFS (pesquisa da primeira profundidade). A travessia do gráfico está visitando exatamente uma vez cada vértice ou nó e aresta, em uma ordem bem definida. Além disso, é muito importante acompanhar os vértices visitados, para que o mesmo vértice não seja percorrido duas vezes. No algoritmo Breath First Search, o percurso inicia a partir de um nó ou nó de origem selecionado e o percurso continua pelos nós diretamente conectados ao nó de origem. Em termos mais simples, no algoritmo BFS, deve-se primeiro mover horizontalmente e atravessar a camada atual, após o que deve ser movido para a próxima camada.
Como funciona o algoritmo BFS?
Vamos dar o exemplo do gráfico abaixo.
A tarefa importante em questão é encontrar o caminho mais curto em um gráfico enquanto percorre os nós. Quando percorremos um gráfico, o vértice passa de um estado não descoberto para um estado descoberto e finalmente se torna completamente descoberto. Deve-se notar que é possível ficar preso em algum momento ao percorrer um gráfico e um nó pode ser visitado duas vezes. Portanto, podemos empregar um método para marcar os nós depois que ele muda o estado de não ser descoberto para ser completamente descoberto.
Podemos ver na imagem abaixo que os nós podem ser marcados nos gráficos à medida que são completamente descobertos, marcando-os em preto. Podemos começar no nó de origem e, à medida que a travessia progride em cada nó, eles podem ser marcados para serem identificados.
O percurso começa a partir de um vértice e depois viaja para as arestas de saída. Quando uma aresta vai para um vértice não descoberto, é marcada como descoberta. Mas quando uma aresta vai para um vértice completamente descoberto ou descoberto, ela é ignorada.
Para um gráfico direcionado, cada aresta é visitada uma vez e, para um gráfico não direcionado, é visitada duas vezes, ou seja, uma vez ao visitar cada nó. O algoritmo a ser usado é decidido com base em como os vértices descobertos são armazenados. No algoritmo BFS, a fila é usada onde o vértice mais antigo é descoberto primeiro e depois se propaga pelas camadas a partir do vértice inicial.
Etapas são executadas para um algoritmo BFS
As etapas abaixo são executadas para um algoritmo BFS.
- Em um dado gráfico, vamos começar a partir de um vértice, ou seja, no diagrama acima, é o nó 0. O nível em que esse vértice está presente pode ser indicado como Camada 0.
- O próximo passo é encontrar todos os outros vértices adjacentes ao vértice inicial, ou seja, o nó 0 ou imediatamente acessíveis a partir dele. Em seguida, podemos marcar esses vértices adjacentes para estarem presentes na Camada 1.
- É possível chegar ao mesmo vértice devido a um loop no gráfico. Portanto, devemos viajar apenas para os vértices que devem estar presentes na mesma camada.
- Em seguida, o vértice pai do vértice atual em que estamos é marcado. O mesmo deve ser realizado para todos os vértices na Camada 1.
- Em seguida, o próximo passo é encontrar todos esses vértices, a uma única aresta de todos os vértices da Camada 1. Esse novo conjunto de vértices estará na Camada 2.
- O processo acima é repetido até que todos os nós sejam percorridos.
Exemplo:
Vamos pegar o exemplo do gráfico abaixo e entender como o algoritmo BFS funciona. Geralmente, em um algoritmo BFS, uma fila é usada para enfileirar os nós enquanto atravessa os nós.
No gráfico acima, primeiro o nó 0 deve ser visitado e esse nó está na fila de espera da fila abaixo:
Depois de visitar o nó 0, o nó vizinho de 0, 1 e 2 é colocado na fila. A fila pode ser representada como abaixo: 
Em seguida, o primeiro nó da fila 2 é visitado. Após a visita do nó 2, a fila pode ser representada como abaixo:
Depois de visitar o nó 2, 5 será colocado na fila e, como não há nós vizinhos não visitados para o nó 5, ainda que 5 esteja na fila, mas não será visitado duas vezes.
Em seguida, o primeiro nó na fila é 1 que será visitado. Os nós vizinhos 3 e 4 estão na fila. A fila é representada como abaixo
Em seguida, o primeiro nó na fila é 5 e, para esse nó, não há mais nós vizinhos não visitados. O mesmo vale para os nós 3 e 4 para os quais também não há mais nós vizinhos não visitados.
Portanto, todos os nós são percorridos e, finalmente, a fila fica vazia.
Conclusão
O algoritmo de pesquisa de largura oferece algumas grandes vantagens para recomendá-lo. Uma das muitas aplicações do algoritmo BFS é calcular o caminho mais curto. Além disso, é usado em redes para encontrar nós vizinhos e pode ser encontrado em sites de redes sociais, transmissão em rede e coleta de lixo. Os usuários precisam entender o requisito e o padrão de dados para usá-lo para obter melhor desempenho.
Artigos recomendados
Este foi um guia para o algoritmo BFS. Aqui discutimos o conceito, trabalho, etapas e exemplo de desempenho no algoritmo BFS. Você também pode acessar nossos outros artigos sugeridos para saber mais -
- O que é um algoritmo ganancioso?
- Algoritmo de rastreamento de raios
- Algoritmo de assinatura digital
- O que é o Java Hibernate?
- Criptografia de Assinatura Digital
- BFS vs DFS | As 6 principais diferenças com infográficos