Largura Primeiro Vs Profundidade Primeiro

Quando atravessando uma tree / gráfico Qual é a diferença entre Largura Primeiro e Profundidade primeiro? Qualquer codificação ou exemplo de pseudocódigo seria ótimo.

Esses dois termos diferenciam entre duas maneiras diferentes de andar em uma tree.

É provavelmente mais fácil apenas exibir a diferença. Considere a tree:

A / \ BC / / \ DEF 

Um primeiro percurso de profundidade visitaria os nós nesta ordem

 A, B, D, C, E, F 

Observe que você percorre todo o caminho até uma perna antes de seguir em frente.

Uma passagem em largura primeiro visitaria o nó nessa ordem

 A, B, C, D, E, F 

Aqui nós trabalhamos em todos os níveis antes de descer.

(Note que há alguma ambigüidade nas ordens de travessia, e eu trapaceei para manter a ordem de “leitura” em cada nível da tree. Em qualquer caso eu poderia chegar a B antes ou depois de C, e da mesma forma eu poderia chegar a E antes ou depois de F. Isso pode ou não importar, depende da sua aplicação …)


Ambos os tipos de travessia 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 percurso está na escolha do Container .

  • Para profundidade primeiro use uma pilha. (A implementação recursiva usa a pilha de chamadas …)
  • Para o primeiro uso, 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 recursion termina quando você alcança um nó que não tem filhos, portanto, é garantido que ele termine para charts finitos e acíclicos.


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

 D, B, E, F, C, A 

que é uma variação de profundidade primeiro, onde eu não faço o trabalho em cada nó até que eu esteja andando de volta até a tree. No entanto, visitei os nós superiores no caminho para encontrar seus filhos.

Essa travessia é 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 como um exercício.

Entendendo os termos:

Esta imagem deve dar-lhe a ideia sobre o contexto em que as palavras largura e profundidade são usadas.

Entendendo a Largura e a Profundidade


Pesquisa de Profundidade-Primeiro:

Pesquisa de Profundidade-Primeiro

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

  • Geralmente, ele usa um Stack para lembrar onde deve ir quando atinge um beco sem saída.

  • Regras a seguir: Empurre o primeiro vértice A para a 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 puder seguir a Regra 1, se possível, retire um vértice da pilha.
    3. Se você não puder seguir a Regra 1 ou Regra 2, estará 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 em profundidade são frequentemente usadas em simulações de jogos (e situações de jogo 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 novas escolhas, e assim por diante, em um gráfico de possibilidades em forma de tree em constante expansão.


Pesquisa de largura de canal:

Primeira pesquisa

  • O algoritmo de pesquisa abrangente gosta de ficar o mais próximo possível do ponto de partida.
  • Esse tipo de pesquisa geralmente é implementado usando uma Queue .
  • Regras a seguir: Tornar o início do Vertex A o vértice atual
    1. Visite o próximo vértice não visitado (se houver um) adjacente ao vértice atual, marque-o e insira-o na fila.
    2. Se você não puder executar a Regra 1 porque não há mais vértices não visitados, remova um vértice da fila (se possível) e torne-o o vértice atual.
    3. Se você não puder executar a regra 2 porque a fila está vazia, está feito.
  • 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 em largura primeiro encontra todos os vértices que estão a uma distância do ponto inicial, depois todos os vértices que estão a duas arestas distantes e assim por diante. Isso é útil se você estiver tentando encontrar o caminho mais curto do vértice inicial para um dado vértice.

Espero que isso seja suficiente para entender as buscas de Breadth-First e Depth-First. Para ler mais, recomendo o capítulo Gráficos de um excelente livro de estruturas de dados de Robert Lafore.

Eu acho que seria interessante escrever os dois de uma forma que apenas trocando algumas linhas de código você daria um algoritmo ou outro, de modo que você veria que seu dillema não é tão forte quanto parece ser a princípio .

Eu pessoalmente gosto da interpretação do BFS como inundar uma paisagem: as áreas de baixa altitude serão inundadas primeiro, e somente então as áreas de alta altitude seguiriam. Se você imaginar as altitudes da paisagem como isolinhas, como vemos nos livros de geografia, é fácil ver que o BFS preenche toda a área sob a mesma isolinha ao mesmo tempo, assim como isso seria com a física. Assim, interpretar altitudes como distância ou custo escalado dá uma ideia bastante intuitiva do algoritmo.

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

Eu ainda não vi nenhuma interpretação intuitiva do DFS (apenas o padrão sobre o labirinto, mas não é tão poderoso quanto o BFS e inundações), então para mim parece que o BFS parece se correlacionar melhor com fenômenos físicos como descrito acima, enquanto O DFS se correlaciona melhor com o dilema de escolhas em sistemas racionais (isto é, pessoas ou computadores decidindo qual movimento fazer em um jogo de xadrez ou saindo de um labirinto).

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

Dada esta tree binária:

insira a descrição da imagem aqui

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 

Profundidade Primeiro Traversal:
A travessia não é feita através de níveis inteiros de cada vez. Em vez disso, a travessia mergulha no DEPTH (da raiz até a folha) da tree primeiro. No entanto, é um pouco mais complexo do que simplesmente para cima e para baixo.

Existem três methods:

 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):
Gostei muito desta simples explicação do Quora sobre os methods Depth First Traversal e como eles são comumente usados:
“Na Ordem Traversal irá imprimir valores [em ordem para o BST (tree de pesquisa binária)]”
“O percurso de pré-encomenda é usado para criar uma cópia da [tree de busca binária].”
“A passagem do Postpoint é usada para deletar a [tree de busca binária].”
https://www.quora.com/What-is-the-use-of-pre-order-and-post-order-traversal-of-binary-trees-in-computing