BFS vs DFS – Diferença entre eles

O que é BFS?

BFS é um algoritmo usado para representar graficamente dados ou pesquisar árvores ou atravessar estruturas. 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. 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 largura.

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 ramo antes de retroceder. Ele usa uma estrutura de dados de pilha para lembrar, obter o vértice subsequente e iniciar uma pesquisa sempre que um beco sem saída aparecer em qualquer iteração. A forma completa do DFS é a pesquisa em profundidade.

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

Aqui estão as diferenças importantes entre 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 e depois volta.
A forma completa do BFS é a pesquisa em amplitude.	A forma completa de DFS é Depth First Search.
Ele usa uma fila para acompanhar o próximo local a ser visitado.	Ele usa uma pilha para controlar 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 com o 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 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 ficar preso em loops infinitos.
Se você não encontrar nenhum objetivo, poderá ser necessário expandir muitos nós antes que a solução seja encontrada.	Se você não encontrar nenhum objetivo, poderá ocorrer o retrocesso do nó folha.

Exemplo de BFS

No exemplo de BFS a seguir, 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.

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

Passo 5)

As iterações de passagem são repetidas até que todos os nós sejam visitados.

Exemplo de DFS

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

Passo 1)

Começamos 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.

Passo 3)

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

Passo 4)

Por fim, visitaremos o último vértice 3, ele não possui nenhum nó adjacente não visitado. Concluímos a travessia do gráfico usando o algoritmo DFS.

Aplicações de BFS

Aqui estão as aplicações do BFS:

Gráficos não ponderados

O algoritmo BFS pode facilmente criar o caminho mais curto e uma árvore geradora 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

Mecanismos de busca 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.

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.

Aplicações de DFS

Aqui estão aplicações 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 geradora mínima.

Detectando um ciclo em um gráfico

Um gráfico tem um ciclo se encontrarmos uma aresta posterior durante o DFS. Portanto, devemos executar o DFS para o gráfico e verificar as arestas posteriores.

Encontrando o caminho

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

Classificação Topológica

É usado principalmente para agendar trabalhos a partir de determinadas dependências entre o grupo de trabalhos. Na ciência da computação, é utilizado no escalonamento de instruções, serialização de dados, síntese lógica, determinação da 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 de um labirinto, incluindo nós no caminho existente no conjunto visitado.