BFS vs DFS: saiba a diferença

O que é BFS ?

BFS é um algoritmo que é usado para representar graficamente dados ou árvore de pesquisa 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 então visita todos os nós adjacentes ao nó selecionado. Uma vez 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 árvore binária DFS
• Aplicativos de BFS
• Aplicativos de DFS

O que é DFS?

DFS é um algoritmo para encontrar ou percorrer gráficos ou árvores na direção de 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, nós usei gráfico com 6 vértices.

Exemplo de 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 inseridos na estrutura de dados da fila.

Etapa 4)

Restantes 0 adjacentes e não visitados os nós são visitados, marcados e inseridos na fila.

Etapa 5)

As iterações transversais são repetidas até todos os nós são visitados.

Exemplo de DFS

No seguinte exemplo de DFS, usamos um gráfico não direcionado com 5 vértices.

Etapa 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 nos dados estrutura chamada pilha.

Etapa 2)

Você visitará o elemento , que está no topo da pilha, por exemplo, 1 e vai para seus nós adjacentes. É porque 0 já foi visitado. Portanto, visitamos o vértice 2.

Etapa 3)

Vertex 2 tem um vértice próximo não visitado em 4. Portanto, nós o adicionamos na pilha e o visitamos.

Etapa 4)

Finalmente, visitaremos o último vértice 3, ele não “tem nenhum nó adjacente não visitado. Concluímos o percurso do gráfico usando o algoritmo DFS.

Diferença entre árvore binária BFS e DFS

BFS	DFS
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 de BFS é Pesquisa em Largura.	A forma completa de 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.
BFS atravessa de acordo com o nível da árvore.	DFS atravessa de acordo com a profundidade da árvore.
É implementado usando FI Lista FO.	É implementado usando a lista LIFO.
Requer mais memória em comparação ao DFS.	Requer menos memória em comparação ao BFS.
Este algoritmo fornece a solução de caminho mais superficial.	Este algoritmo não garante a solução do caminho mais superficial.
Não há necessidade de retrocesso no BFS.	Há uma necessidade de retrocesso no DFS.
Você nunca pode ficar preso em loops finitos.	Você pode ser 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.

Aplicativos de BFS

Aqui estão os aplicativos de BFS:

Não ponderados Gráficos:

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:

Os mecanismos de pesquisa ou rastreadores da web podem construir facilmente vários níveis de índices usando 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.

Network Broadcasting:

Um pacote broadcast é guiado pelo algoritmo BFS para encontrar e alcançar todos os nós para os quais tem o endereço.

Aplicativos de DFS

Aqui estão aplicativos importantes de 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.

Localização do caminho:

Podemos nos especializar no algoritmo DFS para pesquisar um caminho entre dois vértices.

Classificação topológica:

É usado principalmente para agendar tarefas de dependências fornecidas entre o grupo de tarefas. 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.

Pesquisando 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.