Uso in tempo reale di un ordine trasversale trasversale

Question

Qualcuno può suggerirmi quando avrei bisogno di un attraversamento dell'ordine di livello (per risolvere qualche scenario pratico/reale)?

Answer 1

Level order traversal è in realtà una ricerca di ampiezza prima, che non è ricorsiva per sua natura.

Da: http://en.wikipedia.org/wiki/Breadth-first_search

Larghezza-prima ricerca può essere utilizzato per risolvere molti problemi in teoria dei grafi, ad esempio:

• Trovare tutti i nodi all'interno di un componente collegato
• Copia Collection, l'algoritmo di Cheney
• Trovare il percorso più breve tra due nodi u e - v (con lunghezza del percorso misurata dal numero di bordi)
• Tes ting un grafico per bipartiteness
• (Reverse) Cuthill-McKee maglia numerazione
metodo
• Ford-Fulkerson per calcolare il flusso massimo in una rete di flusso
• serializzazione/deserializzazione di un albero binario vs serializzazione ordine filtrate, permette l'albero da ricostruire in modo efficiente .

Answer 2

Google Map Direction sta utilizzando Level Order Traversal (BFS) per tutto il tempo.

Gli algoritmi ripetono lo stesso metodo scegliendo il nodo più vicino ai punti di intersezione, selezionando eventualmente il percorso con la lunghezza più breve.

http://blog.hackerearth.com/breadth-first-search-algorithm-example-working-of-gps-navigation