Drevo proti grafu v podatkovni strukturi
Ker sta drevesa in graf nelinearni podatkovni strukturi, ki se uporabljata za reševanje kompleksnih računalniških problemov, je koristno poznati razliko med drevesom in grafom v podatkovni strukturi. Obe podatkovni strukturi predstavljata podatkovne postavke v matematični obliki. Glavni cilj članka je osvetliti pomen nelinearnih podatkovnih struktur. Vključuje tudi ključno razliko med tema dvema podatkovnima strukturama.
Kaj je drevo v podatkovni strukturi?
Drevo je nelinearna podatkovna struktura, v kateri so vsi podatki razvrščeni v nekem razvrščenem zaporedju. Drevo definira končen niz podatkovnih elementov. Vsaka podatkovna postavka se imenuje vozlišče. Obstaja posebno nadrejeno vozlišče, ki se imenuje tudi korensko vozlišče. Vsa druga vozlišča so podrejena vozlišča ali podpodrejena vozlišča. Glavni cilj drevesa je predstaviti hierarhično razmerje med različnimi podatki. Običajno drevo raste v smeri navzgor, drevo strukture podatkov pa navzdol. Vsa podvozlišča, povezana z drevesom, so razdeljena na različne ravni. Binarno drevo je najpogostejši primer nelinearne strukture podatkov. Največja stopnja binarnega drevesa je dve. To pomeni, da sta lahko z vsakim nadrejenim vozliščem povezani največ dve vozlišči.
Kaj je graf v podatkovni strukturi?
Graf je priljubljena nelinearna podatkovna struktura, ki se uporablja za reševanje različnih računalniških problemov. Uporabljajo se za oblikovanje različnih iger in ugank. Grafe lahko razdelimo v številne kategorije. To so:
• Usmerjeni graf: V usmerjenem grafu je vsak rob določen z urejenim parom vozlišč.
• Neusmerjeni graf: V neusmerjenem grafu je vsak rob definiran z neurejenim parom vozlišč
• Povezani graf: V povezani poti obstaja pot od vsake točke do vsake druge točke.
• Nepovezan graf: V nepovezanem grafu pot ne obstaja od nobene točke do katere koli druge točke.
• Uteženi graf: V uteženem grafu je nekaj teže pritrjeno na rob.
• Preprost graf ali več grafov
Podobnosti med drevesom in grafom v podatkovni strukturi
• Drevesa in graf sta nelinearna podatkovna struktura, ki se uporabljata za reševanje kompleksnih računalniških težav.
• Obe podatkovni strukturi uporabljata nadrejeno vozlišče in več podvozlišč.
Kakšna je razlika med drevesom in grafom v podatkovni strukturi?
• Drevo se obravnava kot poseben primer grafa. Imenuje se tudi minimalno povezan graf.
• Vsako drevo je mogoče obravnavati kot graf, vendar vsakega grafa ni mogoče obravnavati kot drevo.
• Lastne zanke in vezja niso na voljo v drevesu kot v primeru grafov.
• Za oblikovanje drevesa potrebujete nadrejeno vozlišče in različna podvozlišča. Za načrtovanje grafa potrebujete oglišča in robove. Rob je par vozlišč.
Zgornja razprava zaključuje, da sta drevo in graf najbolj priljubljeni podatkovni strukturi, ki se uporabljata za reševanje različnih kompleksnih problemov. Grafi so bolj priljubljena podatkovna struktura, ki se uporablja v računalniškem načrtovanju, fizičnih strukturah in inženirstvu. Večina ugank je zasnovana s pomočjo grafične podatkovne strukture. Problem najkrajše razdalje je najpogosteje uporabljena podatkovna struktura. V tej nalogi moramo izračunati najkrajšo razdaljo med dvema vozliščema.
Nadaljnje branje:
