Entendo as diferenças entre DFS e BFS, mas estou interessado em saber quando é mais prático usar um sobre o outro?

Alguém poderia dar exemplos de como o DFS superaria o BFS e vice-versa?

Isso depende muito da estrutura da árvore de pesquisa e do número e localização das soluções (também conhecidas como itens pesquisados).

• Se você sabe que uma solução não está longe da raiz da árvore, uma BFS (primeira pesquisa de largura) pode ser melhor.

• Se a árvore for muito profunda e as soluções forem raras, a DFS (Deep First Search) pode levar um tempo extremamente longo, mas o BFS pode ser mais rápido.

• Se a árvore for muito ampla, um BFS pode precisar de muita memória, por isso pode ser completamente impraticável.

• Se as soluções forem frequentes, mas localizadas no fundo da árvore, o BFS pode ser impraticável.

• Se a árvore de pesquisa for muito profunda, você precisará restringir a profundidade da pesquisa para a primeira pesquisa de profundidade (DFS), de qualquer maneira (por exemplo, com aprofundamento iterativo).

Mas estas são apenas regras de ouro; você provavelmente precisará experimentar.

Pesquisa em profundidade

Pesquisas profundas são frequentemente usadas em simulações de jogos (e situações semelhantes a jogos no mundo real). Em um jogo típico, você pode escolher uma das várias ações possíveis. Cada escolha leva a novas escolhas, cada uma das quais leva a outras opções, e assim por diante, em um gráfico de possibilidades em forma de árvore em constante expansão.

Por exemplo, em jogos como xadrez, jogo da velha quando você decide o que fazer, você pode imaginar mentalmente um movimento, depois as possíveis respostas do seu oponente, suas respostas e assim por diante. Você pode decidir o que fazer vendo qual jogada leva ao melhor resultado.

Apenas alguns caminhos em uma árvore de jogo levam à sua vitória. Alguns levam a uma vitória do seu oponente, quando você chega a esse final, deve voltar ou voltar para um nó anterior e tentar um caminho diferente. Dessa maneira, você explora a árvore até encontrar um caminho com uma conclusão bem-sucedida. Então você faz o primeiro movimento nesse caminho.

Pesquisa pela primeira vez

A busca pela amplitude da primeira possui uma propriedade interessante: primeiro encontra todos os vértices que estão a uma aresta do ponto inicial, depois todos os vértices que estão a duas arestas e assim por diante. Isso é útil se você estiver tentando encontrar o caminho mais curto do vértice inicial para um determinado vértice. Você inicia um BFS e, quando encontra o vértice especificado, sabe que o caminho que você traçou até agora é o caminho mais curto para o nó. Se houvesse um caminho mais curto, o BFS já o teria encontrado.

A pesquisa abrangente pode ser usada para encontrar os nós vizinhos em redes ponto a ponto como o BitTorrent, sistemas de GPS para localizar locais próximos, sites de redes sociais para encontrar pessoas na distância especificada e coisas assim.

Explicação agradável de http://www.programmerinterview.com/index.php/data-structures/dfs-vs-bfs/

Um exemplo de BFS

Aqui está um exemplo de como seria um BFS. É algo como o nível Order Tree Traversal, onde usaremos o QUEUE com abordagem ITERATIVE (principalmente RECURSION terminará no DFS). Os números representam a ordem na qual os nós são acessados ​​em um BFS:

Em uma primeira pesquisa profunda, você começa na raiz e segue um dos ramos da árvore o mais longe possível até encontrar o nó que procura ou atingir um nó folha (um nó sem filhos). Se você acertar um nó folha, continuará a pesquisa no ancestral mais próximo com filhos inexplorados.

Um exemplo de DFS

Aqui está um exemplo de como seria um DFS. Eu acho que o percurso pós-ordem na árvore binária começará o trabalho a partir do nível Leaf primeiro. Os números representam a ordem na qual os nós são acessados ​​em um DFS:

Diferenças entre DFS e BFS

Comparando o BFS e o DFS, a grande vantagem do DFS é que ele possui requisitos de memória muito inferiores aos do BFS, porque não é necessário armazenar todos os ponteiros filhos em cada nível. Dependendo dos dados e do que você está procurando, o DFS ou o BFS pode ser vantajoso.

Por exemplo, dada uma árvore genealógica, se alguém estivesse procurando alguém na árvore que ainda estivesse vivo, seria seguro supor que essa pessoa estaria no fundo da árvore. Isso significa que um BFS levaria muito tempo para atingir esse último nível. Um DFS, no entanto, encontraria a meta mais rapidamente. Mas, se alguém estivesse procurando por um membro da família que morreu há muito tempo, essa pessoa estaria mais perto do topo da árvore. Em seguida, um BFS geralmente seria mais rápido que um DFS. Portanto, as vantagens de ambos variam dependendo dos dados e do que você está procurando.

Mais um exemplo é o Facebook; Sugestão sobre amigos de amigos. Precisamos de amigos imediatos para sugestões de onde podemos usar o BFS. Pode estar encontrando o caminho mais curto ou detectando o ciclo (usando recursão), podemos usar o DFS.

A Primeira Pesquisa de Largura geralmente é a melhor abordagem quando a profundidade da árvore pode variar e você só precisa procurar uma parte da árvore em busca de uma solução. Por exemplo, encontrar o caminho mais curto de um valor inicial para um valor final é um bom lugar para usar o BFS.

A Pesquisa em profundidade primeiro é comumente usada quando você precisa pesquisar em toda a árvore. É mais fácil de implementar (usando recursão) do que o BFS e requer menos estado: enquanto o BFS exige que você armazene toda a 'fronteira', o DFS exige apenas que você armazene a lista de nós-pai do elemento atual.

O DFS é mais eficiente em termos de espaço que o BFS, mas pode ir a profundidades desnecessárias.

Seus nomes são reveladores: se houver uma grande amplitude (grande fator de ramificação), mas uma profundidade muito limitada (por exemplo, número limitado de "movimentos"), o DFS poderá ser mais preferível ao BFS.

No IDDFS

Deve-se mencionar que há uma variante menos conhecida que combina a eficiência de espaço do DFS, mas (cumulativamente) a visitação por ordem de nível do BFS, é o aprofundamento iterativo da pesquisa profunda . Esse algoritmo revisita alguns nós, mas apenas contribui com um fator constante de diferença assintótica.

Quando você aborda essa questão como programador, um fator se destaca: se você estiver usando recursão, a pesquisa profunda será mais simples. de implementar, porque você não precisará manter uma estrutura de dados adicional que contenha os nós ainda a serem explorados.

Aqui está a busca profunda de um gráfico não orientado se você estiver armazenando informações "já visitadas" nos nós:

def dfs(origin):                               # DFS from origin:
    origin.visited = True                      # Mark the origin as visited
    for neighbor in origin.neighbors:          # Loop over the neighbors
        if not neighbor.visited: dfs(next)     # Visit each neighbor if not already visited

Se estiver armazenando informações "já visitadas" em uma estrutura de dados separada:

def dfs(node, visited):                        # DFS from origin, with already-visited set:
    visited.add(node)                          # Mark the origin as visited
    for neighbor in node.neighbors:            # Loop over the neighbors
        if not neighbor in visited:            # If the neighbor hasn't been visited yet,
            dfs(node, visited)                 # then visit the neighbor
dfs(origin, set())

Compare isso com a pesquisa abrangente, em que você precisa manter uma estrutura de dados separada para a lista de nós ainda a visitar, não importa o quê.

Uma vantagem importante do BFS seria que ele pode ser usado para encontrar o caminho mais curto entre dois nós em um gráfico não ponderado. Visto que não podemos usar o DFS para o mesmo .

Para o BFS, podemos considerar o exemplo do Facebook. Recebemos sugestões para adicionar amigos do perfil do FB de outros perfis de amigos. Suponha A-> B, enquanto B-> E e B-> F, então A receberá sugestões para E e F. Eles devem estar usando BFS para ler até o segundo nível. O DFS é mais baseado em cenários em que queremos prever algo com base nos dados que temos da origem ao destino. Como já foi mencionado sobre xadrez ou sudoku. Uma vez que tenho algo diferente aqui, acredito que o DFS deve ser usado para o caminho mais curto, porque o DFS cobrirá todo o caminho primeiro, para que possamos decidir o melhor. Mas como o BFS usará a abordagem gananciosa, pode parecer que esse seja o caminho mais curto, mas o resultado final pode ser diferente. Deixe-me saber se meu entendimento está errado.

Alguns algoritmos dependem de propriedades específicas do DFS (ou BFS) para funcionar. Por exemplo, o algoritmo Hopcroft e Tarjan para localizar componentes conectados a 2 aproveita o fato de que cada nó já visitado encontrado pelo DFS está no caminho da raiz para o nó atualmente explorado.

A seguir, é apresentada uma resposta abrangente ao que você está perguntando.

Em termos simples:

O algoritmo BFS (largura da primeira pesquisa), do nome "Largura", descobre todos os vizinhos de um nó pelas bordas externas do nó e depois descobre os vizinhos não visitados dos vizinhos mencionados anteriormente através de suas bordas externas e assim por diante, até que todos os nós alcançáveis ​​a partir da fonte original são visitados (podemos continuar e pegar outra fonte original se ainda houver nós não visitados e assim por diante). É por isso que ele pode ser usado para encontrar o caminho mais curto (se houver) de um nó (origem original) para outro nó se os pesos das arestas forem uniformes.

O algoritmo DFS (Depth First Search), a partir do nome "Depth", descobre os vizinhos não visitados do nó x descoberto mais recentemente através de suas bordas externas. Se não houver um vizinho não visitado do nó x, o algoritmo recuará para descobrir os vizinhos não visitados do nó (através de suas bordas externas) a partir dos quais o nó x foi descoberto, e assim por diante, até que todos os nós alcançáveis ​​a partir da fonte original sejam visitados (podemos continuar e buscar outra fonte original se ainda houver nós não visitados e assim por diante).

O BFS e o DFS podem estar incompletos. Por exemplo, se o fator de ramificação de um nó for infinito ou muito grande para os recursos (memória) suportarem (por exemplo, ao armazenar os nós a serem descobertos a seguir), o BFS não estará completo, mesmo que a chave pesquisada possa estar à distância de poucas arestas da fonte original. Esse fator de ramificação infinito pode ser devido a escolhas infinitas (nós vizinhos) de um determinado nó a ser descoberto. Se a profundidade for infinita ou muito grande para os recursos (memória) suportarem (por exemplo, ao armazenar os nós a serem descobertos a seguir), o DFS não estará completo, mesmo que a chave pesquisada possa ser o terceiro vizinho da fonte original. Essa profundidade infinita pode ocorrer devido a uma situação em que, para cada nó que o algoritmo descobre, pelo menos uma nova opção (nó vizinho) que antes não era visitada.

Portanto, podemos concluir quando usar o BFS e o DFS. Suponha que estamos lidando com um fator de ramificação limitado gerenciável e uma profundidade limitada gerenciável. Se o nó pesquisado for raso, ou seja, alcançável após algumas arestas da fonte original, é melhor usar o BFS. Por outro lado, se o nó pesquisado for profundo, ou seja, alcançável após muitas arestas da fonte original, é melhor usar o DFS.

Por exemplo, em uma rede social, se queremos procurar pessoas que têm interesses semelhantes a uma pessoa específica, podemos aplicar o BFS dessa pessoa como uma fonte original, porque na maioria das vezes essas pessoas serão seus amigos diretos ou amigos de amigos, ou seja, um ou duas arestas distantes. Por outro lado, se queremos procurar pessoas que têm interesses completamente diferentes de uma pessoa específica, podemos aplicar o DFS dessa pessoa como uma fonte original, porque na maioria das vezes essas pessoas estarão muito longe dele, ou seja, amigo de amigo de amigo. .... ou seja, muitas arestas longe.

Os aplicativos de BFS e DFS também podem variar devido ao mecanismo de pesquisa em cada um. Por exemplo, podemos usar o BFS (assumindo que o fator de ramificação é gerenciável) ou o DFS (assumindo que a profundidade é gerenciável) quando queremos apenas verificar a acessibilidade de um nó para outro sem informações onde esse nó pode estar. Além disso, os dois podem resolver as mesmas tarefas, como a classificação topológica de um gráfico (se houver). O BFS pode ser usado para encontrar o caminho mais curto, com bordas de peso unitário, de um nó (origem original) para outro. Visto que o DFS pode ser usado para esgotar todas as opções devido à sua natureza de aprofundar, como descobrir o caminho mais longo entre dois nós em um gráfico acíclico. Também DFS, pode ser usado para detecção de ciclo em um gráfico.

No final, se tivermos profundidade infinita e fator de ramificação infinito, podemos usar a Pesquisa de Aprofundamento Iterativo (IDS).

De acordo com as propriedades do DFS e BFS. Por exemplo, quando queremos encontrar o caminho mais curto. geralmente usamos bfs, ele pode garantir o 'menor'. mas dfs só pode garantir que podemos vir deste ponto, pode alcançar esse ponto, não pode garantir o 'mais curto'.

Eu acho que depende de quais problemas você está enfrentando.

1. caminho mais curto no gráfico simples -> bfs
2. todos os resultados possíveis -> dfs
3. pesquisa no gráfico (trate a árvore, martix também como gráfico) -> dfs ....

Como as Pesquisas Profundas-Primeiro usam uma pilha à medida que os nós são processados, o retorno é fornecido com o DFS. Como as Pesquisas da Primeira Largura usam uma fila, não uma pilha, para rastrear quais nós são processados, o retorno não é fornecido com o BFS.

Quando a largura da árvore for muito grande e a profundidade for baixa, use o DFS, pois a pilha de recursão não excederá o limite. Use BFS quando a largura for baixa e a profundidade for muito grande para atravessar a árvore.

Este é um bom exemplo para demonstrar que o BFS é melhor que o DFS em certos casos. https://leetcode.com/problems/01-matrix/

Quando implementadas corretamente, ambas as soluções devem visitar células que tenham distâncias maiores que a célula atual +1. Mas o DFS é ineficiente e visitou repetidamente a mesma célula, resultando em complexidade O (n * n).

Por exemplo,

1,1,1,1,1,1,1,1, 
1,1,1,1,1,1,1,1, 
1,1,1,1,1,1,1,1, 
0,0,0,0,0,0,0,0,

Depende da situação em que é usado. Sempre que temos um problema de percorrer um gráfico, fazemos isso com algum objetivo. Quando há um problema de encontrar o caminho mais curto em um gráfico não ponderado, ou descobrir se um gráfico é bipartido, podemos usar o BFS. Para problemas de detecção de ciclo ou qualquer lógica que exija retorno, podemos usar o DFS.