Graf proti drevesu
Graf in drevo se uporabljata v podatkovnih strukturah. Vsekakor obstaja nekaj razlik med grafom in drevesom. Niz vozlišč, ki imajo binarno relacijo, se imenuje graf, medtem ko je drevo podatkovna struktura, ki ima niz vozlišč, povezanih med seboj.
Graf
Graf je niz elementov, ki so povezani z robovi in vsak element je znan kot vozlišče ali oglišče. Z drugimi besedami, graf lahko definiramo kot niz tock in med temi tockami obstaja binarna relacija.
Pri implementaciji grafa so vozlišča implementirana kot objekti ali strukture. Robove lahko predstavljamo na različne načine. Eden od načinov je, da je vsako vozlišče mogoče povezati z nizom incidentnih robov. Če naj bodo informacije shranjene v vozliščih in ne v robovih, potem nizi delujejo kot kazalci na vozlišča in tudi predstavljajo robove. Ena od prednosti tega pristopa je, da je mogoče grafu dodati dodatna vozlišča. Obstoječa vozlišča je mogoče povezati z dodajanjem elementov nizom. Vendar obstaja ena pomanjkljivost, ker je potreben čas, da se ugotovi, ali obstaja rob med vozlišči.
Drug način za to je, da obdržite dvodimenzionalni niz ali matriko M, ki ima logične vrednosti. Obstoj roba od vozlišča i do j je določen z vnosom Mij. Ena od prednosti te metode je ugotoviti, ali obstaja rob med dvema vozliščema.
Drevo
Tree je tudi podatkovna struktura, ki se uporablja v računalništvu. Podobna je strukturi drevesa in ima niz vozlišč, ki so med seboj povezana.
Vozlišče drevesa lahko vsebuje pogoj ali vrednost. Lahko je tudi samostojno drevo ali pa predstavlja ločeno podatkovno strukturo. V drevesni podatkovni strukturi ni nič ali več vozlišč. Če ima vozlišče otroka, se imenuje nadrejeno vozlišče tega otroka. V vozlišču je lahko največ en nadrejeni element. Najdaljša pot navzdol od vozlišča do lista je višina vozlišča. Globina vozlišča je predstavljena s potjo do njegovega korena.
V drevesu se najvišje vozlišče imenuje korensko vozlišče. Korensko vozlišče nima staršev, saj je najvišje. Iz tega vozlišča se začnejo vse drevesne operacije. Z uporabo povezav ali robov je mogoče doseči druga vozlišča iz korenskega vozlišča. Vozlišča na najnižji ravni se imenujejo listna vozlišča in nimajo otrok. Vozlišče, ki ima več podrejenih vozlišč, se imenuje notranje vozlišče ali notranje vozlišče.
Razlika med grafom in drevesom:
• Drevo lahko opišemo kot poseben primer grafa brez lastnih zank in vezij.
• V drevesu ni zank, medtem ko ima graf lahko zanke.
• V grafu so trije nizi, tj. robovi, vozlišča in niz, ki predstavlja njihovo relacijo, medtem ko je drevo sestavljeno iz vozlišč, ki so med seboj povezana. Te povezave se imenujejo robovi.
• V drevesu obstajajo številna pravila, ki določajo, kako lahko pride do povezav vozlišč, medtem ko graf nima pravil, ki bi določala povezavo med vozlišči.
