Larghezza Prima Vs Profondità First

Question

quando si attraversa un albero / Grafico qual è la differenza tra il primo Larghezza e Profondità per primo? Qualsiasi codifica o pseudocodice esempi sarebbe grande.

Answer 1

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

E 'probabilmente più facile solo per mostrare la differenza. Considerare l'albero:

    A
   / \
  B   C
 /   / \
D   E   F

Un profondità primo attraversamento sarebbe visitare i nodi in questo ordine

A, B, D, C, E, F

Si noti che si va fino in fondo giù una gamba prima di passare.

Un ampiezza primo attraversamento sarebbe visitare il nodo in questo ordine

A, B, C, D, E, F

Qui lavoriamo tutto il percorso attraverso ogni livello prima di scendere.

(Si noti che non v'è una certa ambiguità negli ordini traversal, e ho truffato per mantenere l'ordine "lettura" ad ogni livello dell'albero. In entrambi i casi ho potuto ottenere a B prima o dopo C, e allo stesso modo io potrebbe arrivare a e prima o dopo F. Questo può o non può importa, dipende da voi applicazione ...)

---

Entrambi i tipi di attraversamento possono essere raggiunti con la 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.

• profondità prima utilizzare una pila. (L'implementazione ricorsiva utilizza la chiamata stack ...)
• breadth-first utilizzare una coda.

---

L'implementazione ricorsiva appare come

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 è garantito per finire per finita, grafi aciclici.

---

A questo punto, ho ancora un po 'truffato. Con un po 'di intelligenza si può anche lavoro-on i nodi in questo ordine:

D, B, E, F, C, A

che è una variante di profondità prima, in cui non faccio il lavoro ad ogni nodo fino a quando sto camminando di nuovo l'albero. Ho però visitato i nodi più alti sulla strada verso il basso per trovare i loro figli.

Questa attraversamento è abbastanza naturale nella implementazione ricorsiva (utilizzare la riga di "orario alternativo" al di sopra invece della prima linea "Lavoro"), e non anche difficile se si utilizza uno stack esplicito, ma lascio come esercizio.

Answer 2

La comprensione dei termini:

Questa immagine dovrebbe darvi l'idea del contesto in cui le parole ampiezza e profondità vengono utilizzati.

---

Profondità-prima ricerca:

• Profondità-primo algoritmo di ricerca si comporta come se si vuole ottenere il più lontano dal punto di partenza il più rapidamente possibile.

• Si utilizza in genere un Stack per ricordare dove deve andare quando raggiunge un vicolo cieco.

• Regole da seguire: Push primo vertice A al Stack

  1. Se possibile, visitare un vertice non visitata adiacente, segnare come ha visitato, e spingerlo nello stack.
  2. Se non è possibile seguire la Regola 1, poi, se possibile, un vertice pop dallo stack.
  3. Se non è possibile seguire Regola 1 o Regola 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;
  }
  

• : ricerche in profondità sono spesso utilizzati nelle simulazioni di giochi (e di situazioni di gioco simili a Il mondo reale). In un tipico gioco è possibile scegliere una delle diverse azioni possibili. Ogni scelta porta ad ulteriori scelte, ognuno dei quali porta ad ulteriori scelte, e così via in una continua espansione grafico a forma di albero di possibilità.

---

breadth-first ricerca:

• L'algoritmo di ricerca in ampiezza piace stare il più vicino possibile al punto di partenza.
• Questo tipo di ricerca è generalmente implementato utilizzando un Queue.
• Regole da seguire: fare partire Vertice AL vertice corrente
  1. Visita il vertice successivo non visitato (se ce n'è uno) che è adiacente al vertice corrente, segnarlo, e inserirla nella coda.
  2. Se non è possibile effettuare la Regola 1, perché non ci sono vertici più visitati, rimuovere un vertice dalla coda (se possibile) e renderlo il vertice corrente.
  3. Se non è possibile effettuare 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;
  }
  

• : Larghezza-prima ricerca trova prima tutti i vertici che sono un bordo di distanza dal punto di partenza , allora tutti i vertici che sono due bordi di distanza, e così via. Ciò è utile se si sta cercando di trovare il percorso più breve dal vertice di iniziare ad un dato vertice.

Speriamo che dovrebbe essere sufficiente per comprendere l'ampiezza e le ricerche in profondità. Per ulteriori approfondimenti vi consiglio il capitolo grafici da un eccellente strutture di dati libro di Robert Lafore.

Answer 3

Dato questo albero binario:

Larghezza Primo Traversal:
Traverse attraverso ogni livello da sinistra a destra.

"Sono G, i miei figli sono D ed io, i miei nipoti sono 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à Primo Traversal:
Traversal non è fatto su tutta livelli alla volta. Invece, attraversamento tuffa nella profondità (dalla radice alla foglia) dell'albero prima. Tuttavia, è un po 'più complesso della semplice 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

Utilizzo (aka, perché ce ne importa):
Ho davvero apprezzato questo semplice spiegazione Quora della profondità metodi Prima Traversal e come essi sono comunemente usati:
"In-Order Traversal stamperà i valori [in modo che il BST (ricerca binaria albero)]"
"Pre-ordine di attraversamento viene utilizzato per creare una copia del [albero binario di ricerca]."
"Postorder attraversamento viene utilizzata per eliminare il [albero binario di ricerca]."
https://www.quora.com/What-is-the-use-of-pre-order-and-post-order-traversal-of-binary-trees-in-computing

Answer 4

Credo che sarebbe interessante scrivere ciascuno di essi in un modo che solo passando alcune righe di codice darebbe un algoritmo o l'altro, in modo che si vedrà che il vostro dillema non è così forte come sembra essere in un primo momento.

Personalmente, come l'interpretazione di BFS come inondazioni un paesaggio: le zone a bassa quota saranno inondate prima, e solo allora le zone di alta quota avrebbero seguito. Se si immagina le altitudini paesaggio come isolinee come si vede nei libri di geografia, è facile vedere che BFS riempie tutta l'area sotto la stessa ISOLINE, allo stesso tempo, proprio come sarebbe con la fisica. Così, interpretando altitudini la distanza o il costo in scala dà un'idea abbastanza intuitiva dell'algoritmo.

Con questo in mente, si può facilmente adattare l'idea alla base di ricerca in ampiezza per trovare la spanning tree minima facilmente, percorso più breve, e anche molti altri algoritmi di minimizzazione.

Non ho visto alcuna interpretazione intuitiva di DFS ancora (solo quella standard per il labirinto, ma si mangia potente come la BFS uno e inondazioni), quindi per me sembra che BFS sembra correlare meglio con fenomeni fisici come descritto al di sopra, mentre DFS correla meglio con scelte dillema su sistemi razionali (cioè le persone che decidono o computer che si muovono per fare in una partita a scacchi o uscire da un labirinto).

Quindi, per me la differenza tra menzogna sulla quale fenomeno naturale meglio corrisponde al modello di propagazione (transversing) nella vita reale.