Razlika Med Grafom In Drevesom

2024 Avtor: Mildred Bawerman | [email protected]. Nazadnje spremenjeno: 2023-12-16 08:42

Graf vs drevo

Graf in drevo se uporabljata v podatkovnih strukturah. Gotovo je nekaj razlik med grafom in drevesom. Nabor točk z binarno relacijo se imenuje graf, medtem ko je drevo podatkovna struktura, ki ima nabor vozlišč, povezanih med seboj.

Graf

Graf je niz elementov, ki so povezani z robovi, vsak element pa je znan kot vozlišče ali oglišče. Z drugimi besedami, graf lahko definiramo kot množico točk in med njimi obstaja binarna povezava.

Pri izvedbi grafa so vozlišča izvedena kot predmeti ali strukture. Robove lahko predstavimo na različne načine. Eden od načinov je, da je vsako vozlišče mogoče povezati z matriko vpadnih robov. Če naj bodo informacije shranjene v vozliščih in ne v robovih, potem polja delujejo kot kazalci na vozlišča in predstavljajo tudi robove. Ena od prednosti tega pristopa je, da lahko na graf dodamo dodatna vozlišča. Obstoječa vozlišča je mogoče povezati z dodajanjem elementov v nize. Vendar je ena pomanjkljivost, ker je potreben čas, da ugotovimo, ali obstaja rob med vozlišči.

Drug način za to je obdržati dvodimenzionalno matriko ali matriko M, ki ima logične vrednosti. Obstoj roba od vozlišča i do j določa vnos Mij. Ena od prednosti te metode je ugotoviti, ali obstaja rob med dvema vozliščema.

Drevo

Drevo je tudi podatkovna struktura, ki se uporablja v računalništvu. Podobno je strukturi drevesa in ima nabor 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 strukturi podatkov je prisotnih nič ali več vozlišč. Če ima vozlišče otroka, se imenuje nadrejeno vozlišče tega otroka. Vozlišče je lahko največ eno od staršev. Najdaljša pot navzdol od vozlišča do lista je višina vozlišča. Globino vozlišča predstavlja pot do njegovega korena.

V drevesu se najvišje vozlišče imenuje korensko vozlišče. Koreninsko vozlišče nima staršev, saj je najbolj na vrhu. Od tega vozlišča se začnejo vse drevesne operacije. Z uporabo povezav ali robov lahko do drugih vozlišč pridete iz korenskega vozlišča. Vozlišča na najnižji ravni se imenujejo listna vozlišča in nimajo otrok. Vozlišče s številom podrejenih vozlišč se imenuje notranje vozlišče ali notranje vozlišče.

• Drevo lahko opišemo kot poseben primer grafa brez lastnih zank in vezij.

• V drevesu ni zank, medtem ko lahko graf vsebuje zanke.

• V grafu so trije nizi, tj. Robovi, oglišča in niz, ki predstavlja njihovo razmerje, 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 narekovala povezavo med vozlišči.