Graf vs strom
Graf a strom sa používajú v dátových štruktúrach. Medzi Graph a Tree sú určite 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á navzájom prepojenú množinu uzlov.
Graf
Graf je skupina položiek, ktoré sú spojené hranami a každá položka je známa ako uzol alebo vrchol. Inými slovami, graf možno definovať ako množinu 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 dopadajúcich hrán. Ak sa majú informácie ukladať v uzloch, a nie na okrajoch, tieto polia fungujú ako ukazovatele na uzly a tiež predstavujú okraje. Jednou z výhod tohto prístupu je, že do grafu je možné pridať ďalšie uzly. Existujúce uzly je možné prepojiť pridaním prvkov do polí. Existuje však jedna nevýhoda, pretože na určenie, či je medzi uzlami hrana, je potrebný čas.
Iným spôsobom, ako to urobiť, je zachovať dvojrozmerné pole alebo maticu M, ktorá má logické hodnoty. Existencia okraja od uzla i po j je špecifikovaná položkou Mij. Jednou z výhod tejto metódy je zistiť, či existuje hrana medzi dvoma uzlami.
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 spojené.
Uzol stromu môže obsahovať podmienku alebo hodnotu. Môže to byť tiež vlastný strom alebo môže predstavovať samostatnú dátovú štruktúru. V stromovej dátovej štruktúre je nula alebo viac uzlov. Ak má uzol dieťa, potom sa nazýva nadradený uzol tohto dieťaťa. Môže existovať najviac jeden rodič uzla. Najdlhšou cestou nadol od uzla k listu je výška uzla. Hĺbku uzla predstavuje cesta k jeho koreňu.
Na strome sa najvyšší uzol nazýva koreňový uzol. Koreňový uzol nemá žiadnych rodičov, pretože je najvyšší. Od tohto uzla začínajú všetky operácie so stromom. Použitím odkazov alebo hrán možno z koreňového uzla dosiahnuť ďalšie uzly. Uzly na najnižšej úrovni sa nazývajú listové uzly a nemajú žiadne deti. Uzol, ktorý má počet podradených uzlov, sa nazýva vnútorný uzol alebo vnútorný uzol.
• Strom možno označiť ako špecializovaný prípad grafu bez samostatných slučiek a obvodov.
• Na strome nie sú žiadne slučky, zatiaľ čo graf môže mať slučky.
• V grafe sú tri množiny, tj hrany, vrcholy a množina, ktorá predstavuje ich vzťah, zatiaľ čo strom sa skladá z uzlov, ktoré sú navzájom spojené. Tieto spojenia sa označujú ako hrany.
• V strome je veľa pravidiel, ktoré vysvetľujú, ako môže dôjsť k spojeniu uzlov, zatiaľ čo graf nemá žiadne pravidlá, ktoré by diktovali spojenie medzi uzlami.
