iterativo albero camminare

Question

E 'passato un po' di tempo da quando ho preso strutture dati e algoritmi al college, quindi sono rimasto sorpreso di recente da un suggerimento che la ricorsione non può essere il modo (tm) per fare albero di attraversamento. Per qualche ragione iterativo, l'attraversamento in coda non è stata una tecnica che abbia mai usato.

Quali sono, se presenti, i vantaggi della traversata iterativa rispetto a quella ricorsiva? In quali situazioni potrei usare l'una piuttosto che l'altra?

Answer 1

Se si sta eseguendo una ricerca per ampiezza, l'implementazione naturale è di spingere i nodi in una coda, non di ricorrere alla ricorsione.

Se si esegue una ricerca di profondità prima, la ricorsione è il modo più naturale per codificare l'attraversamento. Tuttavia, a meno che il compilatore non ottimizzi la ricorsione della coda nell'iterazione, l'implementazione ricorsiva sarà più lenta di un algoritmo iterativo e morirà con un overflow dello stack su un albero sufficientemente profondo.

Un rapido Python per illustrare la differenza:

#A tree is a tuple of an int and a tree. 
t = (1, (2,(4, (6), (7, (9)))), (3, (5, (8)))) 
def bfs(t): 
    to_visit = [t] 
    while len(to_visit) > 0: 
     c = to_visit[0] 
     if type(c) is int: 
      print c 
     else: 
      print c[0] 
      to_visit.append(c[1]) 
      if len(c) > 2: to_visit.append(c[2]) 
     to_visit = to_visit[1:] 

def dfs(t): 
    if type(t) is int: 
     print t 
     return 
    print t[0] 
    dfs(t[1]) 
    if len(t) > 2: dfs(t[2]) 

bfs(t) 
dfs(t) 

Answer 2

Dipende se si vuole fare in profondità o ampiezza attraversamento. La prima profondità è la più semplice da implementare tramite la ricorsione. Con Breadth-first è necessario mantenere una coda di nodi da espandere in futuro.

Answer 3

Se si dispone di una quantità fissa di memoria dedicata allo stack, come si fa spesso (questo è particolarmente un problema in molte configurazioni JVM Java), la ricorsione potrebbe non funzionare bene se si dispone di un albero profondo (o se la profondità di ricorsione è alto in qualsiasi altro scenario); causerà un overflow dello stack. Un approccio iterativo, che spinge i nodi a visitare una coda (per l'attraversamento simile a BFS) o lo stack (per l'attraversamento di tipo DFS) ha migliori proprietà di memoria in diversi modi, quindi se ciò è importante, usa un approccio iterativo.

Il vantaggio della ricorsione è la semplicità/eleganza dell'espressione, non delle prestazioni. Ricordare che è la chiave per scegliere l'approccio appropriato per un dato algoritmo, dimensione del problema e architettura della macchina.

Answer 4

In realtà si dovrebbe usare la coda per la prima ricerca di ampiezza e impilare per la prima ricerca di profondità, ed eseguire l'algoritmo da un ciclo while. Fare chiamate a funzioni ricorsive può trascinare il programma in modo significativo se si eseguono semplici operazioni mentre si attraversa, e si può causare un sovraccarico di stack, ma in questi giorni si dovrebbe provare veramente difficile vederne uno solo .

Basta avere un hash sul lato per tenere traccia dei nodi già visitati nel caso in cui non sia un albero ma un grafico ben collegato.

Answer 5

Andare con ricorsivo, perché si potrebbe effettivamente ottenere un errore di overflow dello stack, e questo è stackoverflow.com, dopo tutto.