Strom vs graf v dátovej štruktúre
Keďže stromy a graf sú nelineárne dátové štruktúry, ktoré sa používajú na riešenie zložitých počítačových problémov, je užitočné poznať rozdiel medzi stromom a grafom v dátovej štruktúre. Obe dátové štruktúry predstavujú dátové položky v matematickej forme. Hlavným cieľom článku je poukázať na význam nelineárnych dátových štruktúr. Zahŕňa aj kľúčový rozdiel medzi týmito dvoma dátovými štruktúrami.
Čo je to strom v dátovej štruktúre?
Strom je nelineárna dátová štruktúra, v ktorej sú všetky dátové položky usporiadané v nejakom zoradenom poradí. Strom definuje konečnú množinu údajových položiek. Každá dátová položka sa nazýva uzol. Existuje špeciálny nadradený uzol, ktorý sa tiež nazýva koreňový uzol. Všetky ostatné uzly sú podriadené uzly alebo podradené podriadené uzly. Hlavným cieľom stromu je reprezentovať hierarchický vzťah medzi rôznymi dátovými položkami. Normálny strom rastie smerom hore, ale strom štruktúry údajov rastie smerom dole. Všetky poduzly pripojené k stromu sú rozdelené do rôznych úrovní. Binárny strom je najbežnejším príkladom nelineárnej dátovej štruktúry. Maximálny stupeň binárneho stromu je dva. Znamená to, že ku každému rodičovskému uzlu môžu byť pripojené maximálne dva uzly.
Čo je to graf v dátovej štruktúre?
Graf je populárna nelineárna dátová štruktúra, ktorá sa používa na riešenie rôznych počítačových problémov. Používajú sa na navrhovanie rôznych hier a hlavolamov. Grafy možno rozdeliť do mnohých kategórií. Toto sú:
• Orientovaný graf: V orientovanom grafe je každá hrana definovaná usporiadaným párom vrcholov.
• Neorientovaný graf: V neorientovanom grafe je každá hrana definovaná neusporiadaným párom vrcholov
• Prepojený graf: V prepojenej ceste existuje cesta z každého vrcholu do každého druhého vrcholu.
• Nespojený graf: V neprepojenom grafe neexistuje cesta zo žiadneho vrcholu do žiadneho iného vrcholu.
• Vážený graf: Vo váženom grafe je určitá váha pripojená k okraju.
• Jednoduchý graf alebo viacnásobný graf
Podobnosti medzi stromom a grafom v dátovej štruktúre
• Stromy aj graf sú nelineárne dátové štruktúry, ktoré sa používajú na riešenie zložitých počítačových problémov.
• Obe dátové štruktúry používajú nadradený uzol a viacero poduzlov.
Aký je rozdiel medzi stromom a grafom v dátovej štruktúre?
• Strom sa považuje za špeciálny prípad grafu. Označuje sa tiež ako minimálne súvislý graf.
• Každý strom môže byť považovaný za graf, ale každý graf nemôže byť považovaný za strom.
• Vlastné slučky a okruhy nie sú v strome dostupné ako v prípade grafov.
• Na navrhovanie stromu potrebujete nadradený uzol a rôzne poduzly. Pre návrh grafu potrebujete vrcholy a hrany. Edge je pár vrcholov.
Vyššie uvedená diskusia dospela k záveru, že strom a graf sú najobľúbenejšie dátové štruktúry, ktoré sa používajú na riešenie rôznych zložitých problémov. Grafy sú populárnejšou dátovou štruktúrou, ktorá sa používa v počítačovom navrhovaní, fyzických štruktúrach a inžinierskej vede. Väčšina hádaniek je navrhnutá pomocou grafovej dátovej štruktúry. Problém najmenšej vzdialenosti je najčastejšie používaná dátová štruktúra. V tomto probléme musíme vypočítať najkratšiu vzdialenosť medzi dvoma vrcholmi.
Ďalšie čítanie:
