Strom vs Graf v dátovej štruktúre
Pretože stromy a graf sú nelineárne dátové štruktúry, ktoré sa používajú na riešenie zložitých problémov s počítačom, 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 zdôrazniť význam nelineárnych dátových štruktúr. Zahŕňa tiež kľúčový rozdiel medzi týmito dvoma dátovými štruktúrami.
Čo je 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 dátových položiek. Každá údajová položka sa nazýva uzol. Existuje špeciálny nadradený uzol, ktorý sa tiež nazýva koreňový uzol. Všetky ostatné uzly sú podradenými uzlami alebo podradenými uzlami. Hlavným cieľom stromu je reprezentovať hierarchický vzťah medzi rôznymi dátovými položkami. Normálny strom rastie v hornom smere, ale strom dátovej štruktúry rastie v dolnom smere. Všetky subuzly 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 sú dva. To znamená, že ku každému nadradenému uzlu je možné pripojiť maximálne dva uzly.
Čo je 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 problémov s počítačom. Používajú sa na navrhovanie rôznych hier a hlavolamov. Grafy je možné rozdeliť do mnohých kategórií. Sú to:
• Directed Graph: V usmernenom grafe je každá hrana definovaná usporiadanou dvojicou vrcholov.
• Neusmernený graf: V neusmernenom grafe je každá hrana definovaná nezoradenou dvojicou vrcholov
• Prepojený graf: V spojenej ceste existuje cesta z každého vrcholu do každého druhého.
• Nepripojený graf: V nepripojenom grafe cesta neexistuje od žiadneho vrcholu k inému.
• Vážený graf: Vo váženom grafe je časť váhy pripevnená k okraju.
• Jednoduchý graf alebo viac grafov
Podobnosti medzi stromom a grafom v dátovej štruktúre
• Stromy a grafy sú nelineárne dátové štruktúry, ktoré sa používajú na riešenie zložitých problémov s počítačom.
• Obe dátové štruktúry používajú nadradený uzol a viac poduzlov.
Aký je rozdiel medzi stromom a grafom v dátovej štruktúre?
• Strom sa považuje za zvláštny prípad grafu. Označuje sa tiež ako minimálne prepojený graf.
• Každý strom možno považovať za graf, ale každý graf nemožno považovať za strom.
• Samočinné slučky a obvody nie sú v strome k dispozícii ako v prípade grafov.
• Pre návrh stromu potrebujete nadradený uzol a rôzne poduzly. Pre návrh grafu potrebujete vrcholy a hrany. Edge je dvojica vrcholov.
Vyššie uvedená diskusia uzatvára, ž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í, vo fyzikálnych štruktúrach a v inžinierskych vedách. Väčšina hlavolamov je navrhnutá pomocou grafickej dátovej štruktúry. Problém s najkratšou vzdialenosťou je najbežnejšie používanou dátovou štruktúrou. V tomto probléme musíme vypočítať najkratšiu vzdialenosť medzi dvoma vrcholmi.
Ďalšie čítanie:
