? En dybde -først-søk er en algoritme som prosedyremessig søker en graf eller trestruktur ved å reise så langt ned treet som det kan før sikkerhetskopiering . Den tid som det tar å fullføre algoritmen avhenger av antallet av noder i grafen. I verste fall må algoritmen besøke hver node i grafen . Tre Grafer

I forbindelse med grafer , er et tre en graf der hver node unntatt opprinnelse " root" node har en enslig forsørger node hvis avstamning spor tilbake til rotnoden . Grafen danner en struktur som minner om et juletre , gradvis utvide og legge til nye noder og barn på hvert nivå . I et tre , er antall barn hver node har treets " forgrening faktor. " Antall generasjoner i treet er treets " dybde ".
Dybde -først-søk

en dybde -først-søk er en metode for å søke gjennom et tre , der algoritmen går ned treet til den finner målnoden . Starter fra rotnoden , går algoritmen ned til neste barnet og da at barnets barnebarn , gjenta prosessen til den finner en barnløs " blad " node. Etter den finner at node, går den tilbake opp til den finner en unexamined node. Hvis det ikke er mer undersøkt noder , stopper det .
Algoritme Tid Kompleksitet

tid til å traversere et tre via dybde -først-søk avhenger av antall av noder i grafen og kanter mellom dem . I verste tilfelle må algoritmen reise gjennom hvert topp-punkt og langs hver kant , slik at den tid det vil ta er antall hjørner og antall kanter , eller "V + E " for tre, antallet kanter er lik nodene minus en , slik at den totale tiden er " 2V - . 1" Hvis hver node i grafen har samme antall barn - en konstant forgrening faktor - så denne gangen er lik den faktoren . opphøyd av treet dybde
Andre hensyn

Når gjennomføre enhver algoritme , avhenger av hastigheten på algoritmen på to faktorer : antall beregninger må det gjøre og tiden som kreves for å få tilgang til ressursene den trenger for å kjøre - vanligvis minne. Jo mer minne et program krever , jo lengre tid tar det å kjøre. En dybde -først-søk må huske de tidligere noder det besøkt , slik verste fall hvor mye minne det krever er lik antall noder i treet.