Ampiezza Primo Vs Profondità Prima

Quando l’Attraversamento di un Albero o di un Grafico qual è la differenza tra l’Ampiezza Primo e Profondità prima? Qualsiasi codificazione o pseudocodice esempi sarebbe grande.

  • Hai controllato wikipedia (profondità di primo, ampiezza primo)? Ci sono esempi di codice su queste pagine, insieme con un sacco di belle immagini.
  • Avevo pensato anche, ma poi gli esempi forniti sono leggermente più bello di quelli che si trovano su wikipedia….
InformationsquelleAutor Ted Smith | 2009-03-26

 

4 Replies
  1. 276

    Questi due termini distinguere tra due diversi modi di camminare un albero.

    È probabilmente più semplice di esporre la differenza. Considerare l’albero:

        A
       /\
      B   C
     /  /\
    D   E   F
    

    Un profondità primo attraversamento avrebbe visitato i nodi in questo ordine

    A, B, D, C, E, F
    

    Notare che si va tutta la strada giù una gamba prima di passare.

    Un ampiezza primo attraversamento vorresti visitare il nodo, in questo ordine

    A, B, C, D, E, F
    

    Qui ci lavoro in tutte le attraverso ogni livello prima di scendere.

    (Nota che c’è una certa ambiguità nell’attraversamento di ordini, e ho imbrogliato per mantenere la “lettura” fine a ogni livello dell’albero. In entrambi i casi ho potuto ottenere a B prima o dopo C, e allo stesso modo ho potuto ottenere a E prima o dopo F. Questo può o non importa, dipende dalla tua applicazione…)


    Entrambi i tipi di attraversamento può essere raggiunto con lo pseudocodice:

    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
    

    La differenza tra i due ordini di attraversamento, sta nella scelta di Container.

    • Per profondità prima utilizzare una pila. (Ricorsiva attuazione utilizza lo stack di chiamate…)
    • Per breadth-first utilizzare una coda.

    L’implementazione ricorsiva sembra

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

    La ricorsione termina quando si raggiunge un nodo che non ha figli, in modo che sia garantita alla fine
    finito, aciclici grafici.


    A questo punto, ho ancora un pò barato. Con un po ‘ di furbizia si può anche sul lavoro i nodi in questo ordine:

    D, B, E, F, C, A
    

    che è una variazione di profondità, dove non faccio il lavoro di ciascun nodo fino a quando sto tornando a piedi dell’albero. Ho tuttavia visitato i nodi più alti sulla strada verso il basso per trovare i loro figli.

    Questa traversata è abbastanza naturale in ricorsiva di attuazione (uso “Alternativo tempo sopra indicato al posto di “Lavoro” della linea), e non troppo difficile se si utilizza un esplicito stack, ma lascio come esercizio.

    • Grazie! Credo che si intende “Lavorare in carico al Nodo”, giusto?
    • Può la pena di notare che è possibile modificare la profondità-prima versione di ottenere prefisso (A, B, D, C, E, F – la prima ad essere presentata), infisso (D, B, A, E, C, F – utilizzato per l’ordinamento: aggiungere come un albero AVL e quindi leggere infisso) o postfix (D, B, E, F, C, A l’alternativa proposta) di attraversamento. I nomi sono quelli dati dalla posizione in cui si elabora il root. Va notato che infissa solo fa davvero senso per alberi binari. @batbrat quelli sono i nomi… dato il tempo dal momento che hai chiesto, probabilmente già sapete.
    • grazie per l’aggiunta che in! Sì, so che su questi tipi di attraversamenti e perché Infisso ha senso solo per alberi binari.
    • Come decidere quale soluzione è migliore dal punto di spazio o di tempo la complessità?
    • Dovrebbe essere la stessa per entrambi in linea di principio (dopo tutto, essi utilizzano essenzialmente lo stesso codice). Una domanda più interessante sarebbe l’impatto che essi hanno la cache e a lavorare insieme, ma penso che dipenderà dalla morfologia dell’albero.
  2. 85

    Comprensione dei termini:

    Questa foto dovrebbe dare l’idea del contesto in cui le parole ampiezza e profondità sono utilizzati.

    Ampiezza Primo Vs Profondità Prima


    Depth-First Search:

    Ampiezza Primo Vs Profondità Prima

    • Prima di profondità algoritmo di ricerca agisce come se si vuole ottenere il più lontano
      dal punto di partenza il più rapidamente possibile.

    • Si usa generalmente un Stack ricordare dove si deve andare quando si raggiunge un vicolo cieco.

    • Regole da seguire: Push primo vertice a al Stack

      1. Se possibile, visitare un adiacente non visitati vertice, contrassegnarlo come visitato, e spingere sullo stack.
      2. Se non è possibile seguire la Regola 1, quindi, se possibile, pop un vertice dallo stack.
      3. Se non è possibile seguire la Regola 1 Regola o 2, il gioco è fatto.
    • Codice 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;
      }
      
    • Applicazioni: Prima di profondità ricerche sono spesso utilizzati nelle simulazioni di giochi (e di gioco-come situazioni del mondo reale). In un tipico gioco si può scegliere una delle diverse azioni possibili. Ogni scelta porta a ulteriori scelte, ognuna delle quali conduce ad ulteriori scelte, e così via in una continua espansione a forma di albero grafico di possibilità.


    Di Ricerca Breadth-First:

    Ampiezza Primo Vs Profondità Prima

    • La ricerca breadth-first algoritmo piace rimanere il più vicino possibile
      il punto di partenza.
    • Di ricerca di questo tipo è generalmente implementato utilizzando un Queue.
    • Regole da seguire: Fare a partire da Un Vertice l’attuale vertice
      1. Visitare la prossima non visitati vertice (se c’è) che è adiacente all’attuale vertice, mark ed inserirlo nella coda.
      2. Se non è possibile effettuare la Regola 1, perché non ci sono più non visitati vertici, rimuovere un vertice dalla coda (se possibile) e per rendere l’attuale vertice.
      3. Se non è possibile effettuare la Regola 2, perché la coda è vuota, il gioco è fatto.
    • Codice 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;
      }
      
    • Applicazioni: Breadth-first search prima trova tutti i vertici che sono un bordo di distanza dal punto di partenza, quindi tutti i vertici che sono due bordi e così via. Questo è utile se si sta cercando di trovare il percorso più breve dal vertice di partenza per un dato vertice.

    Speriamo che dovrebbe essere sufficiente per capire l’Ampiezza-in Primo luogo e Prima di Profondità di ricerca. Per una lettura che mi sento di raccomandare il capitolo Grafici da un eccellente strutture di dati libro di Robert Lafore.

    • Io sono più di dieci voto alto a destra, io farei così.
    • si potrebbe attribuire un bounty 😉
    • se ti dico le sue direttive, posso. Non so come fare.
    • href=”https://meta.stackexchange.com/a/184235/388489″>meta.stackexchange.com/a/184235/388489 🙂
    • Grazie @snr, sono così felice di ricevere il mio primo bounty. Apprezzo molto.
    • Grazie @Neve, sono contento che voi ragazzi avete trovato la mia risposta utile.

  3. 3

    Dato questo albero binario:

    Ampiezza Primo Vs Profondità Prima

    In Largo Prima Di Attraversamento:

    Traverse attraverso ogni livello, da sinistra a destra.

    “Io sono G, i miei figli sono D e io, i miei nipoti, B, E, H e K, i loro nipoti sono 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
    

    Profondità Prima Di Attraversamento:

    Di attraversamento non è fatto per l’intera livelli di un tempo. Invece, l’attraversamento di immersioni in PROFONDITÀ (dalla radice alla foglia dell’albero in primo luogo. Tuttavia, è un po ‘ più complesso semplicemente su e giù.

    Ci sono tre metodi:

    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
    

    Di utilizzo (aka, perché non ci interessa):

    Ho davvero apprezzato questo semplice Quora spiegazione della Profondità Primi metodi di Attraversamento e di come essi sono comunemente utilizzati:

    “L’Ordine di Attraversamento, la stampa di valori [in ordine per il BST (binary search tree)]”

    “Il Pre-ordine di attraversamento viene utilizzato per creare una copia del [binary search tree].”

    “Postorder di attraversamento è utilizzato per eliminare il [binary search tree].”

    https://www.quora.com/What-is-the-use-of-pre-order-and-post-order-traversal-of-binary-trees-in-computing

  4. 2

    Penso che sarebbe interessante scrivere di loro in un modo che solo tramite il passaggio di alcune righe di codice che potrebbe darti un algoritmo o di un altro, in modo che, vedrete che il vostro dillema non è così forte come sembra a prima.

    Personalmente mi piace l’interpretazione di BFS come le inondazioni di un paesaggio: la bassa quota delle aree allagate prima, e solo allora, ad alta quota aree vorresti seguire. Se si immagina il paesaggio altitudini come isolinee come vediamo nei libri di geografia, è facile vedere che BFS riempie tutta l’area sotto la stessa isoline, al tempo stesso, proprio come questo sarebbe con la fisica. Così, interpretando altitudini come distanza o scalati costo dà una bella idea intuitiva di algoritmo.

    Con questo in mente, si può facilmente adattare l’idea dietro la larghezza di ricerca per trovare il minimo spanning tree facilmente, percorso più breve, e anche molti altri algoritmi di minimizzazione.

    Non ha ancora vedere qualsiasi interpretazione intuitiva del DFS di sicurezza (solo standard, quella del labirinto, ma non è potente come la BFS uno e inondazioni), quindi per me sembra che BFS sembra correlare meglio i fenomeni fisici come descritto in precedenza, mentre il DFS correla meglio con scelte dillema su sistemi razionali (cioè persone o computer di decidere quale mossa fare su un gioco di scacchi o di un labirinto).

    Quindi, per me la differenza tra menzogne su cui un fenomeno naturale che meglio si adatta al loro modello di propagazione (transversing) nella vita reale.

    • Si può realizzare con un algoritmo simile, basta usare lo stack per DFS e coda per BFS. Il problema con il BFS è che avete bisogno di tenere traccia di tutti i nodi visto finora. DFS in fisica.. immagino alternativa universi e si desidera uno con la vita, tutti i bambini di root, sono diversi big-bang e andare tutto il senso giù per l’universo morte, non la vita? si torna per l’ultima biforcazione e provare un’altra volta, fino a quando tutti sono esausti e si passa alla prossima big-bang, l’impostazione di nuove leggi fisiche per il nuovo universo. super intuitivo. un buon problema è trovare un modo con il cavallo in una scacchiera.

Lascia un commento