Amplitude Primeira Vs Profundidade Primeiro

StackOverflow https://stackoverflow.com/questions/687731

Pergunta

Quando Atravessando uma árvore / Gráfico qual é a diferença entre Amplitude Primeira e profundidade em primeiro lugar? Quaisquer exemplos de codificação ou pseudocódigo seria ótimo.

Foi útil?

Solução

Estes dois termos diferenciar entre duas maneiras diferentes de andar uma árvore.

É provavelmente mais fácil apenas para expor a diferença. Considere a árvore: 

    A
   / \
  B   C
 /   / \
D   E   F

A profundidade primeira travessia iria visitar os nós nesta ordem 

A, B, D, C, E, F

Observe que você percorrer todo o caminho abaixo uma perna antes de prosseguir.

A amplitude primeira travessia iria visitar o nó nesta ordem 

A, B, C, D, E, F

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

(Note que há alguma ambiguidade nas ordens de passagem, e eu enganei para manter a ordem "leitura" em cada nível da árvore. Em ambos os casos eu poderia chegar a B antes ou depois C, e também I poderia chegar a e antes ou depois F. Isto pode ou não matéria, depende de sua aplicação ...)

Os dois tipos de percurso pode ser alcançado 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 mentiras de passagem na escolha do Container.

  • Para profundidade primeira usar uma pilha. (A implementação recursiva usa a chamada-stack ...)
  • Para em largura utilizar uma fila.

Os olhares de implementação recursiva como 

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

As extremidades recursão quando você chegar a um nó que não tem filhos, por isso é garantido para acabar por finito, gráficos acíclicos.

Neste ponto, eu ainda enganado um pouco. Com um pouco de esperteza você também pode trabalho-on os nós nesta ordem: 

D, B, E, F, C, A

que é uma variação da profundidade, da onde eu não fazer o trabalho em cada nó até que eu estou andando de volta até a árvore. Tenho no entanto visitou os nós mais elevados no caminho para baixo para encontrar seus filhos.

Esta travessia é bastante natural a implementação recursiva (usar a linha de "time Alternate" acima em vez da primeira linha "Trabalho"), e não muito difícil se você usar uma pilha explícita, mas vou deixar isso como um exercício.

Outras dicas

Compreender os termos:

Esta imagem deve dar-lhe a idéia sobre o contexto em que as palavras amplitude e profundidade são usados.

Entendimento amplitude e profundidade

Depth-Primeira Pesquisa:

Depth-Primeira Search

  • algoritmo de busca em profundidade age como se ele quer ficar o mais longe a partir do ponto de partida o mais rápido possível.

  • Ela geralmente usa uma Stack se lembrar onde ele deve ir quando se chega a um beco sem saída.

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

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

  • 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;
}

  • Applications : pesquisas em profundidade são frequentemente utilizados em simulações de jogos (e jogo-como situações em o mundo real). Em um jogo típico você pode escolher uma das várias acções possíveis. Cada escolha leva a novas escolhas, cada qual leva a outras opções, e assim por diante em um gráfico de árvore em forma cada vez maior de possibilidades.

em largura Pesquisa:

em largura Search

  • O algoritmo de busca em largura gosta de ficar o mais próximo possível ao ponto de partida.
  • Este tipo de pesquisa é geralmente implementado usando uma Queue.
  • As regras a seguir: tornar o arranque Vertex Um vértice atual
    1. Visite o próximo vértice não visitado (se houver) que é adjacente ao vértice atual, marcá-lo e inseri-lo na fila.
    2. Se você não pode realizar Regra 1 porque não há são vértices mais não visitados, remover um vértice da fila (se possível) e torná-lo o vértice atual.
    3. Se você não pode realizar Regra 2 porque a fila está vazia, você 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;
}

  • Applications : em largura procurar primeiras descobertas todos os vértices que são uma borda de distância do ponto de partida , então todos os vértices que são duas bordas de distância, e assim por diante. Isso é útil se você está tentando encontrar o caminho mais curto a partir do vértice inicial para um dado vértice.

Esperamos que isso deve ser suficiente para a compreensão da em largura e pesquisas em profundidade. Para ler mais Eu recomendaria o capítulo Gráficos de um excelente dados estruturas Reserve por Robert Lafore.

Dada esta árvore binária:

enter descrição da imagem aqui

Amplitude Primeira Travessia:
Traverse em cada nível da esquerda para a direita.

"eu sou L, os filhos estão D e I, são os netos 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:
Traversal não é feito através dos níveis inteiros de cada vez. Em vez disso, mergulhos de passagem para a profundidade (da raiz às folhas) da primeira árvore. No entanto, é um pouco mais complexa do que simplesmente cima e para baixo.

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

Usage (aka, por que nós nos importamos):
Eu realmente gostei desta explicação simples Quora da profundidade métodos Primeira transversal e como eles são comumente utilizados:
"In-Order Traversal imprimirá valores [Para que o BST (árvore de busca binária)]"
"Pre-order traversal é usado para criar uma cópia do [árvore de busca binária]."
"Pós-ordem transversal é usado para apagar o [árvore de busca 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 ambos de uma forma que apenas mudando algumas linhas de código iria dar-lhe um algoritmo ou de outra, de modo que você vai ver que seu dillema não é tão forte como parece estar em primeiro lugar.

Eu, pessoalmente, como a interpretação de BFS como inundando a paisagem: as áreas de baixa altitude será inundada primeiro, e só então as áreas de grande altitude se seguiria. Se você imaginar as altitudes de paisagem como isolinhas como vemos em livros de geografia, é fácil ver que BFS preenche toda a área sob o mesmo isolinha, ao mesmo tempo, como isso seria com a física. Assim, interpretando altitudes como a distância ou custo escalado dá uma ideia bastante intuitivo do algoritmo.

Com isto em mente, você pode facilmente adaptar a idéia por trás busca em largura para encontrar a árvore geradora mínima facilmente, caminho mais curto, e também muitos algoritmos outra minimização.

Eu não ver qualquer interpretação intuitiva de DFS ainda (somente o padrão sobre o labirinto, mas ela não é tão poderoso como o BFS um e inundações), então para mim parece que BFS parece correlacionar-se melhor com os fenômenos físicos como descrito acima, enquanto DFS correlaciona melhor com escolhas dillema em sistemas racionais (ou seja, pessoas ou computadores decisivos que se movem para fazer em um jogo de xadrez ou sair de um labirinto).

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

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top