Obsah

• Srovnávací tabulka
• Definice stromu
• Vlastnosti stromu:
• Definice grafu
• Vlastnosti grafu:
• Závěr

Strom a graf spadají do kategorie nelineární datové struktury, kde strom nabízí velmi užitečný způsob reprezentace vztahu mezi uzly v hierarchické struktuře a graf sleduje síťový model. Strom a graf se liší tím, že stromová struktura musí být spojena a nesmí mít nikdy smyčky, zatímco v grafu taková omezení neexistují.

Nelineární datová struktura sestává ze souboru prvků, které jsou rozloženy v rovině, což znamená, že mezi prvky neexistuje žádná taková sekvence, jaká existuje v lineární datové struktuře.

1. 1. Srovnávací tabulka
   2. Definice
   3. Klíčové rozdíly
   4. Závěr

Srovnávací tabulka

Základ pro srovnání	Strom	Graf
Cesta	Pouze jeden mezi dvěma vrcholy.	Je povoleno více cest.
Kořenový uzel	Má přesně jeden kořenový uzel.	Graf nemá kořenový uzel.
Smyčky	Nejsou povoleny žádné smyčky.	Graf může mít smyčky.
Složitost	Méně složité	Složitější
Traversální techniky	Předobjednat, In-order a Post-order.	Hledání podle šířky a hloubky jako první.
Počet hran	n-1 (kde n je počet uzlů)	Není definovaný
Typ modelu	Hierarchický	Síť

Definice stromu

A strom je konečný soubor datových položek, které se obvykle nazývají uzly. Jak je uvedeno výše, strom je nelineární datová struktura, která uspořádá datové položky v seřazeném pořadí. Používá se k zobrazení hierarchické struktury mezi různými datovými prvky a organizuje data do větví, které se vztahují k informacím. Přidání nové hrany ve stromu má za následek vytvoření smyčky nebo obvodu.

Existuje několik typů stromů, jako je binární strom, binární vyhledávací strom, strom AVL, vláknitý binární strom, B-strom atd. Komprese dat, ukládání souborů, manipulace s aritmetickým výrazem a herní stromy jsou některé z aplikací stromu datová struktura.

Vlastnosti stromu:

• V horní části stromu je označen uzel známý jako kořen stromu.
• Zbývající datové položky jsou rozděleny na disjunktní podmnožiny označované jako podstrom.
• Strom je výškově roztažen směrem dolů.
• Musí být připojen strom, což znamená, že musí existovat cesta od jednoho kořene ke všem ostatním uzlům.
• Neobsahuje žádné smyčky.
• Strom má okraje n-1.

Se stromy jsou spojeny různé termíny, jako je koncový uzel, hrana, úroveň, stupeň, hloubka, les atd. Mezi těmito pojmy jsou některé níže popsané.

• Okraj - Linka spojující dva uzly.
• Úroveň - Strom je rozdělen do úrovní tak, že kořenový uzel je na úrovni 0. Potom jsou jeho bezprostřední děti na úrovni 1 a jeho bezprostřední děti jsou na úrovni 2 atd. Až do koncového nebo listového uzlu.
• Stupeň - Je to počet podstromů uzlu v daném stromu.
• Hloubka - Je to maximální úroveň jakéhokoli uzlu v daném stromu a také známá jako výška.
• Terminál uzel - Uzel nejvyšší úrovně je terminálový uzel, zatímco ostatní uzly s výjimkou terminálového a kořenového uzlu jsou známé jako ne-terminálové uzly.

Definice grafu

A graf je také matematická nelineární datová struktura, která může představovat různé druhy fyzické struktury. Skládá se ze skupiny vrcholů (nebo uzlů) a sady hran, které spojují dva vrcholy. Vrcholy v grafu jsou znázorněny jako bod nebo kruhy a hrany jsou zobrazeny jako oblouky nebo úsečky. Hrana je představována E (v, w), kde v a w jsou páry vrcholů. Odstranění okraje z obvodu nebo připojeného grafu vytvoří podgraf, který je stromem.

Grafy jsou rozděleny do různých kategorií, jako jsou směrované, neřízené, připojené, nepřipojené, jednoduché a více grafy. Počítačová síť, dopravní systém, sociální síťový graf, elektrické obvody a projektování jsou některé z aplikací struktury grafových dat. Používá se také v manažerské technice pojmenované jako PERT (technika hodnocení a přezkumu programu) a CPM (metoda kritické cesty), ve které je analyzována struktura grafu.

Vlastnosti grafu:

• Vrchol v grafu může být spojen s libovolným počtem dalších vrcholů pomocí hran.
• Okraj může být přesměrován nebo nasměrován.
• Hranu lze zvážit.

V grafu také používáme různé termíny, jako jsou sousední vrcholy, cesta, cyklus, stupeň, připojený graf, kompletní graf, vážený graf atd. Pojďme porozumět některým z těchto termínů.

• Sousední vrcholy - Vrchol a sousedí s vrcholem b, pokud existuje hrana (a, b) nebo (b, a).
• Cesta - Cesta z náhodného vrcholu w je sousední posloupností vrcholů.
• Cyklus - Je to cesta, kde první a poslední vrchol jsou stejné.
• Stupeň - Jedná se o několik okrajů dopadajících na vrchol.
• Připojený graf - Pokud existuje cesta od náhodného vrcholu k jinému vrcholu, pak se tento graf označuje jako připojený graf.

1. Ve stromu existuje pouze jedna cesta mezi libovolnými dvěma vrcholy, zatímco graf může mít jednosměrné a obousměrné cesty mezi uzly.
2. Ve stromu je přesně jeden kořenový uzel a každé dítě může mít pouze jednoho rodiče. Naproti tomu v grafu neexistuje koncept kořenového uzlu.
3. Strom nemůže mít smyčky a vlastní smyčky, zatímco graf může mít smyčky a vlastní smyčky.
4. Grafy jsou složitější, protože mohou mít smyčky a samočinné smyčky. Na rozdíl od toho jsou stromy ve srovnání s grafem jednoduché.
5. Strom je procházen pomocí technik předobjednávky, pořadí a posloupnosti. Na druhou stranu, pro průchod grafu používáme BFS (Breadth First Search) a DFS (Depth First Search).
6. Strom může mít okraje n-1. Naopak v grafu není předdefinován počet hran a záleží na grafu.
7. Strom má hierarchickou strukturu, zatímco graf má síťový model.

Závěr

Graf a strom jsou nelineární datové struktury, které se používají k řešení různých složitých problémů. Graf je skupina vrcholů a hran, kde hrana spojuje dvojici vrcholů, zatímco strom je považován za minimálně připojený graf, který musí být spojen a bez smyček.