Rozdiel medzi grafom a stromom

Graf vs strom

Graf a strom sa používajú v dátových štruktúrach. Určite existujú určité rozdiely medzi grafom a stromom. Súbor vrcholov, ktoré majú binárny vzťah, sa nazýva graf, zatiaľ čo strom je dátová štruktúra, ktorá má navzájom prepojené množiny 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. Hrany môžu byť znázornené rôznymi spôsobmi. Jedným zo spôsobov je to, že každý uzol môže byť spojený s radom dopadajúcich hrán. Ak sa majú informácie ukladať skôr v uzloch ako v okrajoch, potom polia pôsobia 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í. Je tu však jedna nevýhoda, pretože je potrebný čas, aby sa zistilo, či je medzi uzlami hrana.

Iným spôsobom, ako to dosiahnuť, je udržať dvojrozmerné pole alebo maticu M, ktorá má booleovské hodnoty. Existencia okraja z uzla i až j je špecifikovaná v položke Mij. Jednou z výhod tejto metódy je zistenie, či je medzi dvoma uzlami 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ť stav alebo hodnotu. Môže to byť aj strom samostatne alebo môže predstavovať samostatnú dátovú štruktúru. V stromovej štruktúre údajov sú prítomné nulové alebo viac uzlov. Ak má uzol dieťa, potom sa nazýva jeho rodičovský uzol. Môže existovať najviac jeden rodič uzla. Najdlhšia cesta smerom dole z uzla do krídla je výška uzla. Hĺbku uzla predstavuje cesta k jeho koreňu.

V strome sa najvyšší vrchol nazýva koreňový uzol. Koreňový uzol nemá rodičov, pretože je najvyšší. Z tohto uzla sa začnú všetky stromové operácie. Použitím odkazov alebo hrán je možné získať ďalšie uzly z koreňového uzla. Uzly najvyššej úrovne 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.