Grafas prieš medį
Duomenų struktūrose naudojami grafikas ir medis. Tikrai yra tam tikrų skirtumų tarp Grafo ir medžio. Viršūnių rinkinys, turintis dvejetainį ryšį, vadinamas grafiku, o medis yra duomenų struktūra, turinti mazgų, susietų vienas su kitu, rinkinį.
Grafikas
Grafas yra elementų, sujungtų briaunomis, rinkinys ir kiekvienas elementas yra žinomas kaip mazgas arba viršūnė. Kitaip tariant, grafą galima apibrėžti kaip viršūnių rinkinį ir tarp šių viršūnių yra dvejetainis ryšys.
Įgyvendinant grafiką, mazgai įgyvendinami kaip objektai arba struktūros. Kraštai gali būti pavaizduoti įvairiais būdais. Vienas iš būdų yra tai, kad kiekvienas mazgas gali būti susietas su incidentų briaunų masyvu. Jei informacija turi būti saugoma mazguose, o ne kraštuose, masyvai veikia kaip rodyklės į mazgus ir taip pat žymi kraštus. Vienas iš šio metodo privalumų yra tai, kad į grafiką galima įtraukti papildomų mazgų. Esamus mazgus galima sujungti pridedant elementus į masyvus. Tačiau yra vienas trūkumas, nes norint nustatyti, ar tarp mazgų yra briauna, reikia laiko.
Kitas būdas tai padaryti – išlaikyti dvimatį masyvą arba matricą M, turinčią Būlio reikšmes. Krašto egzistavimas nuo mazgo i iki j nurodomas įrašu Mij. Vienas iš šio metodo privalumų yra išsiaiškinti, ar tarp dviejų mazgų yra briauna.
Medis
Medis taip pat yra kompiuterių moksle naudojama duomenų struktūra. Jis panašus į medžio struktūrą ir turi mazgų, susietų vienas su kitu, rinkinį.
Medžio mazge gali būti sąlyga arba reikšmė. Tai taip pat gali būti atskiras medis arba gali būti atskira duomenų struktūra. Medžio duomenų struktūroje yra nulis ar daugiau mazgų. Jei mazgas turi antrinį mazgą, jis vadinamas pirminiu to vaiko mazgu. Gali būti ne daugiau kaip vienas mazgo tėvas. Ilgiausias kelias žemyn nuo mazgo iki lapo yra mazgo aukštis. Mazgo gylis rodomas keliu iki jo šaknies.
Medyje aukščiausias mazgas vadinamas šakniniu mazgu. Šakninis mazgas neturi tėvų, nes jis yra aukščiausias. Nuo šio mazgo prasideda visos medžio operacijos. Naudojant nuorodas arba kraštus, iš šakninio mazgo galima pasiekti kitus mazgus. Apatinio lygio mazgai vadinami lapų mazgais ir jie neturi vaikų. Mazgas, kuriame yra antrinių mazgų, vadinamas vidiniu mazgu arba vidiniu mazgu.
Skirtumas tarp grafiko ir medžio:
• Medį galima apibūdinti kaip specializuotą grafiko atvejį, kuriame nėra saviciklų ir grandinių.
• Medyje nėra kilpų, o grafike gali būti kilpų.
• Grafike yra trys rinkiniai, t. y. briaunos, viršūnės ir rinkinys, nurodantis jų ryšį, o medį sudaro mazgai, kurie yra sujungti vienas su kitu. Šios jungtys vadinamos briaunomis.
• Medyje yra daug taisyklių, nurodančių, kaip gali atsirasti mazgų jungtys, o grafikas neturi taisyklių, nurodančių ryšį tarp mazgų.
