? En djup - först sökning är en algoritm som formellt söker en graf eller trädstruktur genom att resa så långt ner trädet eftersom det kan innan du backar . Tiden att algoritmen tar att avsluta beror på antalet noder i grafen. I värsta fall måste algoritmen besöka varje nod i grafen . Träd Grafer
Inom ramen för grafer , är ett träd ett diagram, i vilket varje nod utom ursprunget "root" nod har en enda förälder nod vars härstamning spår tillbaka till rotnoden . Grafen bildar en struktur som liknar en julgran , successivt utöka och lägga till nya noder och barn på varje nivå . I ett träd , är antalet barn varje nod har trädets " förgreningar faktor . " Antalet generationer i trädet är trädets " djup . "
Djupet-först sökning
en djup - först sökning är en metod för att söka igenom ett träd , där algoritmen går ned trädet tills den hittar målnoden . Börja från roten noden , går algoritmen ner till nästa barn och då barns barnbarn , upprepa processen tills den hittar en barnlös " löv " nod . Efter den finner att noden , går det tillbaka upp tills den hittar en ogranskad nod . Om det inte finns några fler undersökta noder , stannar den . Addera ditt Algoritm Time Complexity
tid att korsa ett träd via djup - först sökning beror på antalet av hörn i grafen och kanterna mellan dem . I värsta fall måste algoritmen färdas genom varje vertex och utmed varje kant , så den tid det kommer att ta är antalet hörn och antalet kanter , eller "V + E." För ett träd, det antal kanter är lika med noderna minus ett , så den totala tiden är " 2V - . 1 " Om varje nod i grafen har samma antal barn - en konstant förgrening faktor - då denna tid är lika med denna faktor . upphöjt till av trädets djup
Andra överväganden
Vid genomförandet någon algoritm , beror hastigheten av algoritmen på två faktorer : antalet beräkningar måste det gör och den tid som krävs för att komma åt de resurser som behövs för att köra - oftast minne . Ju mer minne ett program kräver , desto längre tid tar att köra . En djup - först sökning måste komma ihåg de tidigare noder det besökte , så det värsta fallet mängd minne som krävs är lika med antalet noder i trädet .
