Čo je časová zložitosť je prehľadávanie do hĺbky ?

Prehľadávanie do hĺbky je algoritmus , ktorý procesne hľadá štruktúru grafu alebo stromové cestovania , ak sa stromu , ako je možné pred zálohovaním . Čas , ktorý trvá až do konca algoritmus , závisí od počtu uzlov v grafe . V najhoršom prípade , algoritmus musí navštíviť každý uzol v grafe . Strom Grafy

súvislosti grafov , strom je graf , v ktorom každý uzol okrem pôvodu " root " uzol má jeden nadradený uzol , ktorého línie stopy späť do koreňového uzla . Graf tvorí štruktúru podobnú ako u vianočného stromu , bude postupne rozširovať a pridávať nové uzly a deti na každej úrovni . Vo stromu , počet detí má každý uzol je na strome v " vetvenia faktor . " Počet generácií vo stromu stromu je " hĺbka " .
Prehľadávanie do hĺbky

prehľadávania do hĺbky je metóda prehľadávanie stromu , v ktorom algoritmus chodí dole zo stromu , kým nenájde cieľový uzol . Od koreňového uzla , algoritmus prechádzky dole na ďalšie dieťa , a potom to dieťa vnúča , opakovanie procesu , kým nenájde bezdetný " list" uzol . Potom, čo zistí , že uzol , to ide späť až do roku zistí , že je nepreskúmaná uzol . Ak nie sú k dispozícii žiadne ďalšie skúmanej uzly , zastaví sa .
Algoritmus Časová náročnosť

čas prejsť na strom pomocou prehľadávania do hĺbky závisí od počtu vrcholov v grafe a hrany medzi nimi . V najhoršom prípade , algoritmus musí cestovať cez každý vrchol a pozdĺž každej hrany , tak dlho to bude trvať je počet vrcholov a počet hrán , alebo " V + E. " pre drevo , počet hrany sa rovná uzlov mínus jedna , takže celková doba je " 2V - . 1 " , ak každý uzol v grafe má rovnaký počet detí , - konštantný faktor vetvenia - potom je tento čas sa rovná faktora zdvihol k sile hĺbky stromu
Ďalšie úvahy

Pri vykonávaní akejkoľvek algoritmus , rýchlosť algoritmu závisí na dvoch faktoroch : . počet výpočtov musia byť robiť a čas potrebný prístup k prostriedkom k svojmu chodu potrebuje - zvyčajne pamäť . Čím viac pamäte program vyžaduje , tým dlhšie trvá spustiť . Prehľadávanie do hĺbky je nutné pamätať na predchádzajúcu uzly ich navštívil , takže v najhoršom prípade množstvo pamäti to vyžaduje , je rovná počtu uzlov v strome .

• Predchádzajúca strana: Ako zvýšiť Vektor v MATLAB 
• Ďalšia strana: Ako vykonať binárny strom pomocou Pascal