Largura primeiro versus profundidade primeiro

Ao atravessar uma árvore / gráfico, qual é a diferença entre a largura primeiro e a profundidade primeiro? Qualquer exemplo de codificação ou pseudocódigo seria ótimo.

Esses dois termos diferenciam duas maneiras diferentes de andar em uma árvore.

Provavelmente é mais fácil exibir a diferença. Considere a árvore:

    A
   / \
  B   C
 /   / \
D   E   F

Uma primeira travessia em profundidade visitaria os nós nesta ordem

A, B, D, C, E, F

Observe que você desce uma perna antes de seguir em frente.

Uma primeira travessia de largura visitaria o nó nesta ordem

A, B, C, D, E, F

Aqui nós trabalhamos todo o caminho através de cada nível antes de ir para baixo.

(Observe que há alguma ambiguidade nas ordens de travessia, e eu trapacei para manter a ordem de "leitura" em cada nível da árvore. Em ambos os casos, eu poderia chegar a B antes ou depois de C e, da mesma forma, poderia E antes ou depois de F. Isso pode ou não importar, depende da sua aplicação ...)

Ambos os tipos de passagem podem ser alcançados com o pseudocódigo:

Store the root node in Container
While (there are nodes in Container)
   N = Get the "next" node from Container
   Store all the children of N in Container
   Do some work on N

A diferença entre as duas ordens de travessia está na escolha de Container.

• Para profundidade, use primeiro uma pilha. (A implementação recursiva usa a pilha de chamadas ...)
• Para amplitude, use uma fila.

A implementação recursiva parece

ProcessNode(Node)
   Work on the payload Node
   Foreach child of Node
      ProcessNode(child)
   /* Alternate time to work on the payload Node (see below) */

A recursão termina quando você alcança um nó que não tem filhos; portanto, é garantido que ele termine para gráficos acíclicos finitos.

Neste ponto, eu ainda trapacei um pouco. Com um pouco de esperteza, você também pode trabalhar nos nós nesta ordem:

D, B, E, F, C, A

que é uma variação de profundidade primeiro, onde não faço o trabalho em cada nó até voltar a subir na árvore. No entanto, visitei os nós mais altos no caminho para encontrar seus filhos.

Esse percurso é bastante natural na implementação recursiva (use a linha "Tempo alternativo" acima, em vez da primeira linha "Trabalho"), e não é muito difícil se você usar uma pilha explícita, mas deixarei isso como um exercício.

Compreendendo os termos:

Essa imagem deve lhe dar uma idéia do contexto em que as palavras largura e profundidade são usadas.

Pesquisa em profundidade:

• O algoritmo de busca em profundidade atua como se quisesse ficar o mais longe possível do ponto de partida o mais rápido possível.

• Geralmente usa a Stackpara lembrar para onde deve ir quando chega a um beco sem saída.

• Regras a seguir: Empurre o primeiro vértice A para o Stack

  1. Se possível, visite um vértice não visitado adjacente, marque-o como visitado e empurre-o na pilha.
  2. Se você não pode seguir a Regra 1, se possível, solte um vértice da pilha.
  3. Se você não pode seguir a Regra 1 ou 2, está pronto.

• Código Java:

  public void searchDepthFirst() {
      // Begin at vertex 0 (A)
      vertexList[0].wasVisited = true;
      displayVertex(0);
      stack.push(0);
      while (!stack.isEmpty()) {
          int adjacentVertex = getAdjacentUnvisitedVertex(stack.peek());
          // If no such vertex
          if (adjacentVertex == -1) {
              stack.pop();
          } else {
              vertexList[adjacentVertex].wasVisited = true;
              // Do something
              stack.push(adjacentVertex);
          }
      }
      // Stack is empty, so we're done, reset flags
      for (int j = 0; j < nVerts; j++)
          vertexList[j].wasVisited = false;
  }
  

• Aplicações : 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.

Primeira pesquisa de largura:

• O algoritmo de busca em primeiro lugar gosta de ficar o mais próximo possível do ponto de partida.
• Esse tipo de pesquisa geralmente é implementado usando a Queue.
• Regras a seguir: Tornar o vértice A inicial o vértice atual
  1. Visite o próximo vértice não visitado (se houver) adjacente ao vértice atual, marque-o e insira-o na fila.
  2. Se você não pode executar a Regra 1 porque não há mais vértices não visitados, remova um vértice da fila (se possível) e faça dele o vértice atual.
  3. Se você não pode executar a Regra 2 porque a fila está vazia, está pronto.

• Código Java:

  public void searchBreadthFirst() {
      vertexList[0].wasVisited = true;
      displayVertex(0);
      queue.insert(0);
      int v2;
      while (!queue.isEmpty()) {
          int v1 = queue.remove();
          // Until it has no unvisited neighbors, get one
          while ((v2 = getAdjUnvisitedVertex(v1)) != -1) {
              vertexList[v2].wasVisited = true;
              // Do something
              queue.insert(v2);
          }
      }
      // Queue is empty, so we're done, reset flags
      for (int j = 0; j < nVerts; j++) 
          vertexList[j].wasVisited = false;
  }
  

• Aplicações : A pesquisa de largura em primeiro lugar localiza primeiro 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.

Esperamos que isso seja suficiente para entender as pesquisas de Largura-Primeiro e Profundidade-Primeiro. Para uma leitura mais aprofundada, eu recomendaria o capítulo Gráficos de um excelente livro de estruturas de dados de Robert Lafore.

Dada esta árvore binária:

Largura da primeira travessia :
Atravesse cada nível da esquerda para a direita.

"Eu sou G, meus filhos são D e eu, meus netos são B, E, H e K, seus netos são A, C, F"

- Level 1: G 
- Level 2: D, I 
- Level 3: B, E, H, K 
- Level 4: A, C, F

Order Searched: G, D, I, B, E, H, K, A, C, F

Primeira travessia de profundidade: a
travessia não é realizada em níveis inteiros de cada vez. Em vez disso, a travessia mergulha primeiro na PROFUNDIDADE (da raiz à folha) da árvore. No entanto, é um pouco mais complexo do que simplesmente subir e descer.

Existem três métodos:

1) PREORDER: ROOT, LEFT, RIGHT.
You need to think of this as a recursive process:  
Grab the Root. (G)  
Then Check the Left. (It's a tree)  
Grab the Root of the Left. (D)  
Then Check the Left of D. (It's a tree)  
Grab the Root of the Left (B)  
Then Check the Left of B. (A)  
Check the Right of B. (C, and it's a leaf node. Finish B tree. Continue D tree)  
Check the Right of D. (It's a tree)  
Grab the Root. (E)  
Check the Left of E. (Nothing)  
Check the Right of E. (F, Finish D Tree. Move back to G Tree)  
Check the Right of G. (It's a tree)  
Grab the Root of I Tree. (I)  
Check the Left. (H, it's a leaf.)  
Check the Right. (K, it's a leaf. Finish G tree)  
DONE: G, D, B, A, C, E, F, I, H, K  

2) INORDER: LEFT, ROOT, RIGHT
Where the root is "in" or between the left and right child node.  
Check the Left of the G Tree. (It's a D Tree)  
Check the Left of the D Tree. (It's a B Tree)  
Check the Left of the B Tree. (A)  
Check the Root of the B Tree (B)  
Check the Right of the B Tree (C, finished B Tree!)  
Check the Right of the D Tree (It's a E Tree)  
Check the Left of the E Tree. (Nothing)  
Check the Right of the E Tree. (F, it's a leaf. Finish E Tree. Finish D Tree)...  
Onwards until...   
DONE: A, B, C, D, E, F, G, H, I, K  

3) POSTORDER: 
LEFT, RIGHT, ROOT  
DONE: A, C, B, F, E, D, H, K, I, G

Uso (aka, por que nos importamos):
Eu realmente gostei desta explicação simples do Quora sobre os métodos do Profundity First Traversal e como eles são comumente usados:
"O Traversal em ordem imprimirá valores [em ordem para a BST (árvore de pesquisa binária)] "
" O percurso de pré-encomenda é usado para criar uma cópia da [árvore de pesquisa binária]. "
"O percurso da ordem posterior é usado para excluir a [árvore de pesquisa binária]."
https://www.quora.com/What-is-the-use-of-pre-order-and-post-order-traversal-of-binary-trees-in-computing

Eu acho que seria interessante escrever os dois de uma maneira que somente alternando algumas linhas de código lhe desse um algoritmo ou outro, para que você veja que seu dillema não é tão forte quanto parece ser a princípio .

Pessoalmente, gosto da interpretação do BFS como inundação de uma paisagem: as áreas de baixa altitude serão inundadas primeiro e somente então as áreas de alta altitude se seguirão. Se você imaginar as altitudes da paisagem tão isoladas quanto os livros de geografia, é fácil ver que o BFS preenche toda a área sob o mesmo isoline ao mesmo tempo, assim como seria com a física. Assim, interpretar altitudes como distância ou custo escalado fornece uma idéia bastante intuitiva do algoritmo.

Com isso em mente, você pode adaptar facilmente a ideia por trás da primeira pesquisa de largura para encontrar facilmente a árvore de abrangência mínima, o caminho mais curto e também muitos outros algoritmos de minimização.

Ainda não vi nenhuma interpretação intuitiva do DFS (apenas a padrão sobre o labirinto, mas não é tão poderosa quanto a do BFS e a inundação); portanto, para mim, parece que o BFS parece se correlacionar melhor com os fenômenos físicos, conforme descrito acima, enquanto O DFS se correlaciona melhor com o dillema de escolhas em sistemas racionais (ou seja, pessoas ou computadores decidindo qual mover-se em um jogo de xadrez ou sair de um labirinto).

Então, para mim, a diferença entre mentiras sobre qual fenômeno natural melhor combina com seu modelo de propagação (transversal) na vida real.