Graf vs strom
Graf a strom sa používajú v dátových štruktúrach. Medzi grafom a stromom určite existujú určité rozdiely. Množina vrcholov s binárnym vzťahom sa nazýva graf, zatiaľ čo strom je dátová štruktúra, ktorá má množinu vzájomne prepojených uzlov.
Graph
Graf je množina položiek, ktoré sú spojené hranami a každá položka je známa ako uzol alebo vrchol. Inými slovami, graf môže byť definovaný ako množina vrcholov a medzi týmito vrcholmi existuje binárny vzťah.
Pri implementácii grafu sú uzly implementované ako objekty alebo štruktúry. Okraje môžu byť znázornené rôznymi spôsobmi. Jedným zo spôsobov je, že každý uzol môže byť spojený s poľom incidentných hrán. Ak majú byť informácie uložené v uzloch a nie v hranách, potom polia fungujú ako ukazovatele na uzly a tiež predstavujú hrany. Jednou z výhod tohto prístupu je, že do grafu je možné pridať ďalšie uzly. Existujúce uzly môžu byť spojené pridaním prvkov do polí. Existuje však jedna nevýhoda, pretože na určenie, či medzi uzlami existuje hranica, je potrebný čas.
Iný spôsob, ako to urobiť, je ponechať dvojrozmerné pole alebo maticu M, ktorá má booleovské hodnoty. Existencia hrany z uzla i do j je špecifikovaná záznamom Mij. Jednou z výhod tejto metódy je zistiť, či medzi dvoma uzlami existuje hrana.
Strom
Strom je tiež dátová štruktúra používaná v informatike. Je podobná štruktúre stromu a má množinu uzlov, ktoré sú navzájom prepojené.
Uzol stromu môže obsahovať podmienku alebo hodnotu. Môže to byť aj vlastný strom alebo môže predstavovať samostatnú dátovú štruktúru. V stromovej dátovej štruktúre je prítomných nula alebo viac uzlov. Ak má uzol potomka, potom sa nazýva rodičovský uzol tohto potomka. V uzle môže byť maximálne jeden rodič. Najdlhšia zostupná cesta od uzla k listu je výška uzla. Hĺbka uzla je reprezentovaná cestou k jeho koreňu.
V strome sa najvyšší uzol nazýva koreňový uzol. Koreňový uzol nemá rodičov, pretože je najvyšší. Z tohto uzla začínajú všetky operácie so stromami. Pomocou prepojení alebo hrán je možné dosiahnuť ďalšie uzly z koreňového uzla. Uzly na najnižšej úrovni sa nazývajú listové uzly a nemajú žiadne deti. Uzol, ktorý má počet podriadených uzlov, sa nazýva vnútorný uzol alebo vnútorný uzol.
Rozdiel medzi grafom a stromom:
• Strom možno opísať ako špecializovaný prípad grafu bez vlastných slučiek a okruhov.
• V strome nie sú žiadne slučky, zatiaľ čo graf môže mať slučky.
• V grafe sú tri množiny, t. j. hrany, vrcholy a množina, ktorá predstavuje ich vzťah, zatiaľ čo strom pozostáva z uzlov, ktoré sú navzájom spojené. Tieto spojenia sa označujú ako hrany.
• V strome je množstvo pravidiel, ktoré vysvetľujú, ako môže dôjsť k spojeniam uzlov, zatiaľ čo graf nemá žiadne pravidlá, ktoré by diktovali spojenie medzi uzlami.
