O que é BFS?
BFS é um algoritmo usado para representar graficamente dados ou pesquisar árvores ou estruturas transversais. 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. 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. A forma completa do BFS é a pesquisa em amplitude.
Neste BSF vs. Tutorial de árvore binária DFS, você aprenderá:
- O que é BFS?
- O que é DFS?
- Exemplo de BFS
- Exemplo de DFS
- Diferença entre BFS e DFS Binary Tree
- Aplicações de BFS
- Aplicações de DFS
O que é DFS?
DFS é um algoritmo para encontrar ou percorrer gráficos ou árvores na direção da profundidade. A execução do algoritmo começa no nó raiz e explora cada ramificação antes de retroceder. Ele usa uma estrutura de dados de pilha para lembrar, para obter o vértice subsequente e para iniciar uma pesquisa, sempre que um beco sem saída aparecer em qualquer iteração. A forma completa do DFS é a pesquisa em profundidade.
Exemplo de BFS
No seguinte exemplo de DFS, usamos um gráfico com 6 vértices.
Exemplo de 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.
Etapa 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.
Etapa 5)
As iterações de travessia são repetidas até que todos os nós sejam visitados.
Exemplo de DFS
No seguinte exemplo de DFS, usamos um gráfico não direcionado com 5 vértices.
Passo 1)
Começamos a partir do vértice 0. O algoritmo começa colocando-o na lista visitada e simultaneamente colocando todos os seus vértices adjacentes na estrutura de dados chamada pilha.
Passo 2)
Você visitará o elemento, que está no topo da pilha, por exemplo, 1 e irá para seus nós adjacentes. É porque 0 já foi visitado. Portanto, visitamos o vértice 2.
Etapa 3)
O vértice 2 tem um vértice próximo não visitado em 4. Portanto, nós o adicionamos na pilha e o visitamos.
Passo 4)
Finalmente, visitaremos o último vértice 3, ele não possui nenhum nó adjacente não visitado. Concluímos o percurso do gráfico usando o algoritmo DFS.
Diferença entre BFS e DFS Binary Tree
BFS | DFS |
O BFS encontra o caminho mais curto para o destino. | O DFS vai para a parte inferior de uma subárvore, depois retrocede. |
A forma completa do BFS é Pesquisa em Largura. | A forma completa do DFS é Pesquisa em profundidade. |
Ele usa uma fila para rastrear o próximo local a ser visitado. | Ele usa uma pilha para rastrear o próximo local a ser visitado. |
O BFS percorre de acordo com o nível da árvore. | O DFS percorre de acordo com a profundidade da árvore. |
É implementado usando a lista FIFO. | É implementado usando a lista LIFO. |
Requer mais memória em comparação ao DFS. | Requer menos memória em comparação com o BFS. |
Este algoritmo fornece a solução do caminho mais raso. | Este algoritmo não garante a solução do caminho mais raso. |
Não há necessidade de retrocesso no BFS. | É necessário retroceder no DFS. |
Você nunca pode ficar preso a loops finitos. | Você pode ficar preso em loops infinitos. |
Se você não encontrar nenhum objetivo, pode precisar expandir muitos nós antes que a solução seja encontrada. | Se você não encontrar nenhum objetivo, o retrocesso do nó folha pode ocorrer. |
Aplicações de BFS
Aqui estão os aplicativos do BFS:
Gráficos não ponderados:
O algoritmo BFS pode criar facilmente 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:
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:
Os 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.
Transmissão da rede:
Um pacote transmitido é guiado pelo algoritmo BFS para encontrar e alcançar todos os nós para os quais possui o endereço.
Aplicações de DFS
Aqui estão aplicativos importantes do DFS:
Gráfico Ponderado:
Em um gráfico ponderado, a travessia do gráfico DFS gera a árvore de caminho mais curto e a árvore de abrangência mínima.
Detectando um ciclo em um gráfico:
Um gráfico tem um ciclo se encontrarmos uma borda posterior durante o DFS. Portanto, devemos executar o DFS para o gráfico e verificar as bordas posteriores.
Encontrando o caminho:
Podemos nos especializar no algoritmo DFS para pesquisar um caminho entre dois vértices.
Classificação Topológica:
Ele é usado principalmente para agendar jobs das dependências fornecidas entre o grupo de jobs. Na ciência da computação, ele é usado no agendamento de instruções, serialização de dados, síntese lógica, determinando a ordem das tarefas de compilação.
Pesquisa de componentes fortemente conectados de um gráfico:
É usado no gráfico DFS quando há um caminho de cada vértice no gráfico para outros vértices restantes.
Resolvendo quebra-cabeças com apenas uma solução:
O algoritmo DFS pode ser facilmente adaptado para pesquisar todas as soluções para um labirinto, incluindo nós no caminho existente no conjunto visitado.
PRINCIPAIS DIFERNCES:
- O BFS encontra o caminho mais curto para o destino, enquanto o DFS vai para a parte inferior de uma subárvore e, em seguida, retrocede.
- A forma completa do BFS é Pesquisa em Largura, enquanto a forma completa do DFS é Pesquisa em Profundidade.
- O BFS usa uma fila para rastrear o próximo local a ser visitado. enquanto o DFS usa uma pilha para rastrear o próximo local a ser visitado.
- O BFS percorre de acordo com o nível da árvore, enquanto o DFS percorre de acordo com a profundidade da árvore.
- O BFS é implementado usando a lista FIFO, por outro lado o DFS é implementado usando a lista LIFO.
- No BFS, você nunca pode ficar preso em loops finitos, enquanto no DFS você pode ficar preso em loops infinitos.