Complessità del tempo DFS

DFS sta per la prima ricerca. Si riferisce a come vengono visitati i nodi di un albero fino a quando non si trova il nodo desiderato. Per semplicità, tutti i nodi in questo articolo devono essere visitati. L'idea è di vedere tutti i nodi, con ogni nodo visitato una volta. Un nodo è anche chiamato vertice. La prima ricerca di profondità può essere in uno dei tre ordini: pre-ordine, in ordine o post-ordine. L'attraversamento del preordine viene utilizzato in questo articolo. Questo articolo utilizza il seguente albero per illustrare il pre-ordine per la prima ricerca:

Un ramo nell'albero è chiamato bordo. Questo articolo mira a illustrare ciò che è noto come complessità temporale per la ricerca di profondità. DFS viene prima spiegato brevemente. C ++ viene utilizzato per il illustrazione del codice.

Attraversamento del preordine per la prima ricerca

L'algoritmo è il seguente:

1) Visita il vertice corrente.
2) Attraversare il sotto-albero sinistro del vertice corrente in modo ricorsivo.
3) Attraversare il sotto-albero destro del vertice corrente in modo ricorsivo.

Per l'albero precedente, il primo vertice da visitare è un. Questo è il vertice attuale. Attraversando ricorsivamente il sotto-albero sinistro e quindi il sotto-tree destro significa visitare B mentre la visita di C viene registrata nella memoria da visitare in seguito.

A B, B è il vertice corrente. Attraversando ricorsivamente il sotto-albero sinistro e quindi il sotto-tree destro significa visitare E mentre la visita di F viene registrata nella memoria da visitare in seguito.

A E, E è il vertice attuale. E non ha sotto-albero sinistro o destro (nessun bordi). L'ultima registrazione in memoria per la visita è stata il sotto-albero destro (bordo) per b. Il sotto-albero destro per B è costituito da F preceduto dal suo bordo. A questo punto, F viene visitato.

La registrazione precedente in memoria per la visita ora è il sotto-albero destro (bordo) per un. Il sotto-albero giusto per un registrato è costituito da C seguito dai suoi bordi e bambini. A questo punto, C viene visitato. C ha tre bordi. Secondo l'algoritmo, si accede al bordo sinistro.

Quando si accede il bordo sinistro, viene visitato G. Non c'è bambino per G. Con l'algoritmo, H condivide lo stesso genitore con G, e come è sulla destra di G, viene visitato dopo.

"Io" sembra essere sulla destra di H e condivide lo stesso genitore con H. Con l'algoritmo, qualsiasi nodo a destra di un altro nodo deve essere visitato dopo la visita del nodo. Non importa se il nodo appena visitato è sulla destra di un altro nodo. Quindi "io" viene visitato dopo.

Non c'è nodo a destra di "io". C e tutti i suoi discendenti sono stati visitati. Tuttavia, si noti che esiste un nodo a destra di C. Questo nodo è d. Dall'algoritmo, qualsiasi nodo a destra di un altro nodo deve essere visitato dopo il nodo (visitato). Non importa se il nodo visitato era sulla destra di qualche altro nodo. Quindi D verrà visitato dopo.

D ha due figli, J e K. J è a sinistra di k. J è visitato prima di K.

L'algoritmo di ricerca di profondità può essere riassunto come segue: dopo aver visitato la radice, visitare il vertice sinistro mentre scende in modo ricorsivo a sinistra. Dal vertice più a sinistra in basso, visitare i fratelli destro di quel vertice, quindi salire ricorsivamente sull'albero, verso destra e scendere di tanto in tanto in modo appropriato.

Con ciò, la sequenza DFS dell'albero precedente è: A, B, E, F, C, G, H, I, D, J, K.

Complessità temporale

L'albero precedente ha 11 vertici e 10 bordi. Se l'albero è ben studiato, la scansione dell'intero albero coinvolgerà 11 vertici e 10 bordi. Questo è un apprezzamento della velocità del funzionamento della prima ricerca. È la complessità del tempo. È scritto come:

O (| v |+| e |)

Dove | V | è il numero di vertici (nodi) e | e | è il numero di bordi. Per questo albero, il totale è 21 = 11 + 10. La "O" deve essere lì.

Struttura per l'albero

L'organizzazione degli alberi può essere descritta come segue:

Vertex A: Bambini: B, C, D
Vertex B: Bambini: E, F
Vertex C: Bambini: G, H, i
Vertex D: Bambini: J, K
Vertice e
Vertex f
Vertice g
Vertice h
Vertex i
Vertex j
Vertice k

L'albero precedente verrà conservato in un non ordinato_map dei vettori. Un vertice è una chiave e i bambini sono i valori del vettore della chiave. I vertici da e a k non hanno figli.

Coding C ++

Il programma può iniziare con la seguente intestazione:

#includere
#includere
#includere
Utilizzo dello spazio dei nomi std;

Codifica C ++ per i vettori non ordinati

UNORDED_MAP-of-vettori viene creato con il seguente codice:

UNORDERD_MAP > umv = 'a', 'b', 'c', 'd',
'B', 'e', 'f',
'C', 'g', 'h', 'i',
'D', 'j', 'k',
'E', ,
'F', ,
'G', ,
'H', ,
'IO', ,
'J', ,
'K', ;

Questo può essere posizionato appena sotto l'intestazione precedente.

La funzione di profondità-prima

È una funzione ricorsiva che stampa ogni vertice (nodo) visitato. È:

void DepthFirstSearch (char genitore)
cout << parent << "; //print vertex
per (int i = 0; iDepthFirstSearch (UMV [genitore] [i]);

Dopo aver stampato il vertice sinistro, il per loop avrebbe stampato i vertici giusti. Il per loop ha il richiamo.

Funzione principale C ++

Una funzione principale adatta per il programma è:

int main (int argc, char ** argv)

profondeFirstSearch ('a');
cout << endl;
restituzione 0;

L'algoritmo per la prima ricerca è il seguente:

1) Visita il vertice corrente.
2) Attraversare il sotto-albero sinistro del vertice corrente in modo ricorsivo.
3) Attraversare il sotto-albero destro del vertice corrente in modo ricorsivo.

Questo può essere interpretato come segue: dopo aver visitato la radice, visitare il vertice sinistro, scendendo in modo ricorsivo a sinistra. Dal vertice più a sinistra in basso, visitare i fratelli destro di quel vertice e salire ricorsivamente sull'albero, verso destra, scendendo di tanto in tanto, in modo appropriato.

La complessità temporale per l'algoritmo di ricerca profondità è:

O (| v |+| e |)

Conclusione

DFS sta per la prima ricerca. Si riferisce a come vengono visitati i nodi di un albero fino a quando non si trova il nodo desiderato. Per semplicità, tutti i nodi dell'albero di questo articolo sono stati visitati. L'idea è di visitare tutti i nodi, con ogni nodo visitato una volta. Un nodo è anche chiamato vertice. La prima ricerca di profondità può essere in uno dei tre ordini: pre-ordine, in ordine o post-ordine. In questo articolo, è stato utilizzato il preordine.