Una ricerca depth-first è un algoritmo che proceduralmente cerca una struttura ad albero o grafico viaggiando fino giù l'albero, come si può prima del backup. Il tempo che l'algoritmo prende alla fine dipende dal numero di nodi nel grafico. Nel peggiore dei casi, l'algoritmo deve visitare ogni nodo nel grafico.

Grafici ad albero

Nel contesto dei grafici, un albero è un grafo in cui ogni nodo eccetto l'origine "radice" nodo ha un singolo nodo padre cui tracce di lignaggio torna al nodo radice. Il grafico forma una struttura simile a quella di un albero di Natale, gradualmente espandendo e aggiunta di nuovi nodi e bambini in ogni livello. In un albero, il numero di bambini che ogni nodo ha è dell'albero "branching factor." È il numero di generazioni nella struttura della "profondità" dell'albero.

Ricerca depth-First

Una ricerca depth-first è un metodo di ricerca attraverso un albero, in cui l'algoritmo cammina lungo l'albero fino a individuare il nodo di destinazione. A partire dal nodo radice, l'algoritmo cammina giù per il bambino successivo e quindi nipote di quel bambino, ripetendo il processo finché trova un nodo senza figli "foglia". Dopo che trova quel nodo, cammina indietro fino a quando trova un nodo non esaminato. Se ci sono nodi non più esaminati, si ferma.

Complessità di tempo di algoritmo

Il tempo di attraversare un albero tramite ricerca depth-first dipende dal numero di vertici nel grafico e bordi tra di loro. Nel peggiore dei casi, l'algoritmo deve viaggiare attraverso ogni vertice e lungo ogni bordo, quindi il tempo che ci vorrà è il numero di vertici e il numero di bordi, o "V + E." Per un albero, il numero dei bordi è uguale ai nodi meno uno, quindi il tempo totale è "2V - 1." Se ogni nodo nel grafico ha lo stesso numero di bambini..--un costante fattore di ramificazione - questa volta è uguale a tale fattore elevato alla potenza di profondità dell'albero.

Altre considerazioni

Quando qualsiasi algoritmo di esecuzione, la velocità dell'algoritmo dipende da due fattori: il numero di calcoli che deve fare e il tempo necessario per accedere alle risorse è necessario eseguire..--di solito la memoria. La quantità di memoria un programma richiede, il tempo che impiega per l'esecuzione. Una ricerca depth-first deve ricordare i precedenti nodi che ha visitato, quindi la quantità di caso peggiore di memoria che richiede è uguale al numero di nodi nell'albero.