Esta postagem abordará a diferença entre o algoritmo de pesquisa em profundidade (DFS) e pesquisa em largura (BFS) usado para percorrer/pesquisar árvore ou estrutura de dados de gráfico.
1. Definição
o Pesquisa em profundidade (DFS) algoritmo começa na raiz da árvore (ou algum nó arbitrário para um grafo) e explora o máximo possível ao longo de cada ramo antes backtracking.
o Pesquisa em amplitude (BFS) algoritmo também começa na raiz da árvore (ou algum nó arbitrário de um grafo), mas ao contrário do DFS, ele explora os nós vizinhos primeiro, antes de passar para os vizinhos do próximo nível. Em outras palavras, o BFS explora os vértices na ordem de sua distância do vértice de origem, onde a distância é o comprimento mínimo de um caminho do vértice de origem ao nó.
2. Exemplos
O gráfico a seguir mostra a ordem em que os nós são descobertos no DFS:
O gráfico a seguir mostra a ordem em que os nós são descobertos no BFS:
3. Aplicação
Abaixo estão as aplicações do DFS:
- Encontrar componentes conectados em um gráfico.
- Classificação topológica em um DAG (Gráfico Acíclico Dirigido).
- Encontrar componentes 2/3–(aresta ou vértice)–conectados.
- Encontrar o pontes de um gráfico.
- Encontrar componentes fortemente conectados.
- Resolvendo quebra-cabeças com apenas uma solução, como labirintos.
- Encontrar biconectividade em gráficos e muito mais…
Abaixo estão as aplicações do BFS:
- Copiando a coleta de lixo, o algoritmo de Cheney.
- Encontrando o caminho mais curto entre dois nós
uev, com o comprimento do caminho medido pelo número de arestas (uma vantagem sobre a busca em profundidade). - Testando um gráfico para bipartidarismo.
- Árvore de abrangência mínima para gráfico não ponderado.
- Rastreador da Web.
- Encontrar nós em qualquer componente conectado de um grafo.
- Método de Ford-Fulkerson para calcular o fluxo máximo em uma rede de fluxo.
- Serialização/desserialização de um árvore binária.
4. DFS e BFS para Árvores
Podemos percorrer árvores de várias maneiras em profundidade – primeira ordem ou largura – primeira ordem. A busca em profundidade para árvores pode ser implementada usando pedido antecipado, em ordem, e pós-encomenda, enquanto a busca em largura para árvores pode ser implementada usando passagem de ordem de nível.
Além dessas travessias básicas, vários esquemas mais complexos ou híbridos são possíveis, como pesquisas com profundidade limitada, como profundidade de aprofundamento iterativo – primeira pesquisa.
5. Detalhes de Implementação
No BFS, precisamos manter uma estrutura de dados separada para rastrear os nós da árvore/grafo ainda a serem visitados. Isso é feito facilmente de forma iterativa usando o estrutura de dados da queue.
Ao contrário do BFS, o DFS não precisa de nenhuma estrutura de dados adicional para armazenar os nós de árvore/grafo. A implementação recursivo do DFS usa o ligue para Stack.
6. Complexidade do Tempo
A complexidade de tempo da travessia DFS e BFS é O(V + E), Onde V e E são o número total de vértices e arestas no grafo, respectivamente.
Observe que E pode variar entre O(1) e O(V2), dependendo da densidade do gráfico.
7. Requisitos de Memória
A memória usada pelo DFS/BFS depende muito da estrutura da nossa árvore/grafo. A memória máxima ocupada pelo DFS (ou seja, pela ligue para Stack) é igual à profundidade da árvore, e a memória máxima ocupada pelo BFS é igual à largura da árvore.
8. Quando usar DFS e BFS?
Se soubermos que a solução está em algum lugar no fundo de uma árvore ou longe do vértice de origem no grafo, use DFS. Se soubermos que a solução não está tão longe do vértice de origem, use BFS.
Se nossa árvore for ampla, use o DFS, pois o BFS consumirá muita memória. Da mesma forma, se nossa árvore for muito profunda, escolha BFS em vez de DFS.
Veja também:
Pesquisa em profundidade (DFS) - Perguntas da entrevista e problemas práticos
Pesquisa em amplitude (BFS) - Perguntas de entrevista e problemas de prática