DFS tidskompleksitet

DFS står for dybde-første søk. Det refererer til hvordan noder av et tre blir besøkt til den ønskede noden er lokalisert. For enkelhets skyld skal alle nodene i denne artikkelen besøkes. Tanken er å se alle nodene, med hver node besøkt en gang. En node kalles også et toppunkt. Dybde-første søk kan være i en av tre ordrer: forhåndsbestilling, i orden eller etter ordre. Forhåndsbestilling Traversal brukes i denne artikkelen. Denne artikkelen bruker følgende tre brukes til å illustrere forhåndsbestilling for dybde-første søk:

En gren i treet kalles en kant. Denne artikkelen tar sikte på å illustrere det som er kjent som tidskompleksiteten for dybde-første søk. DFS blir først kort forklart. C ++ brukes til kodeillustrasjon.

Forhåndsbestill traversal for dybde-første søk

Algoritmen er som følger:

1) Besøk det nåværende toppunktet.
2) Kryss det venstre undertræret til det nåværende toppunktet på en rekursiv måte.
3) Kryss det rette undertræren til det nåværende toppunktet på en rekursiv måte.

For det forrige treet er det første toppunktet som besøkes en. Dette er det nåværende toppunktet. Rekursivt krysser det venstre sub-treet og deretter det høyre sub-treet betyr besøk B mens besøket av C blir registrert i minnet som skal besøkes senere.

Ved B er B gjeldende toppunkt. Rekursivt krysser det venstre sub-treet og deretter det høyre undertræren betyr besøk E mens besøket av F blir registrert i minnet som skal besøkes senere.

På E er E er det nåværende toppunktet. E har ingen venstre eller høyre undertrekk (ingen kanter). Den siste innspillingen i minnet for besøk var riktig sub-tree (kant) for b. Høyre sub-tre for B består av F før kanten av kanten. På dette tidspunktet blir F besøkt.

Den forrige innspillingen i minnet for å besøke nå er det rette sub-tree (kant) for en. Det rette undertrekket for en innspilt består av C etterfulgt av kanter og barn. På dette tidspunktet blir C besøkt. C har tre kanter. I følge algoritmen får venstre kant først.

Når venstre kant er tilgjengelig, blir G besøkt. Det er ikke noe barn for G. Av algoritmen deler H den samme forelderen med G, og som den er til høyre for G, besøkes den neste.

“Jeg” er tilfeldigvis til høyre for H og deler samme foreldre med H. Av algoritmen må enhver node til høyre for en annen node besøkes etter at noden ble besøkt. Det spiller ingen rolle om noden nettopp besøkte er til høyre for en annen node. Så "jeg" blir besøkt neste.

Det er ingen node til høyre for “Jeg”. C og alle etterkommere er blitt besøkt. Merk imidlertid at det er en node til høyre for C. Denne noden er d. Av algoritmen må enhver node til høyre for en annen node besøkes etter noden (besøkt). Det spiller ingen rolle om noden som ble besøkt var til høyre for en annen node. Så D besøkes neste.

D har to barn, J og K. J er til venstre for K. J besøkes først før K.

Dybde-første søkealgoritme kan oppsummeres som følger: Etter å ha besøkt roten, besøk venstre toppunkt mens du rekursivt går ned til venstre. Besøk de rette søsknene fra det toppunktet fra venstre toppunkt.

Med det er DFS -sekvensen til det forrige treet: a, b, e, f, c, g, h, i, d, j, k.

Tidskompleksitet

Det forrige treet har 11 hjørner og 10 kanter. Hvis treet er godt lagret, vil skanning av hele treet involvere 11 hjørner og 10 kanter. Dette er en forståelse av hastigheten på driften av dybde-første søk. Det er tidskompleksitet. Det er skrevet som:

O (| v |+| e |)

Hvor | v | er antall hjørner (noder) og | e | er antallet kanter. For dette treet er totalen 21 = 11 + 10. “O” må være der.

Struktur for treet

Treorganisasjonen kan beskrives som følger:

Vertex A: Barn: B, C, D
Vertex B: Barn: E, F
Vertex C: Barn: G, H, I
Vertex D: Barn: J, K
Vertex e
Toppunkt f
Vertex g
Toppunkt h
Toppunkt i
Vertex J
Vertex k

Det forrige treet vil bli lagret i en uordnede_map av vektorer. Et toppunkt er en nøkkel, og barna er verdiene på tastens vektor. Hjørner fra e til k har ingen barn.

C ++ koding

Programmet kan begynne med følgende overskrift:

#inkludere
#inkludere
#inkludere
ved hjelp av navneområdet STD;

C ++ koding for uordnede_map-av-vektorer

Uordnede_map-av-vektorer opprettes med følgende kode:

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

Dette kan plasseres rett under forrige overskrift.

Dybde-første funksjon

Det er en rekursiv funksjon som skriver ut hver toppunkt (node) som er besøkt. Det er:

ugyldig dybdefirstSearch (char foreldre)
cout << parent << "; //print vertex
for (int i = 0; idybdefirstSearch (umv [overordnet] [i]);

Etter å ha skrevet ut venstre toppunkt, ville for-loop trykke de høyre toppunktene. For-loopen har tilbakekallingen.

C ++ hovedfunksjon

En passende hovedfunksjon for programmet er:

int main (int argc, char ** argv)

dybdefirstSearch ('a');
cout << endl;
retur 0;

Algoritmen for dybde-første søk er som følger:

1) Besøk det nåværende toppunktet.
2) Kryss det venstre undertræret til det nåværende toppunktet på en rekursiv måte.
3) Kryss det rette undertræren til det nåværende toppunktet på en rekursiv måte.

Dette kan tolkes som følger: Etter å ha besøkt roten, besøk venstre toppunkt, og rekursivt går ned til venstre. Besøk de rette søsknene fra det toppunktet fra venstre toppunkt.

Tidskompleksiteten for dybde-første søkealgoritme er:

O (| v |+| e |)

Konklusjon

DFS står for dybde-første søk. Det refererer til hvordan noder av et tre blir besøkt til den ønskede noden er lokalisert. For enkelhets skyld har alle nodene av treet i denne artikkelen blitt besøkt. Tanken er å besøke alle nodene, med hver node besøkt en gang. En node kalles også et toppunkt. Dybde-første søk kan være i en av tre ordrer: forhåndsbestilling, i orden eller etter ordre. I denne artikkelen har forhåndsbestillinger blitt brukt.