Vitajte na [www.pocitac.win] Pripojiť k domovskej stránke Obľúbené stránky
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 .