Nelineární datová struktura sestává ze souboru prvků, které jsou rozloženy v rovině, což znamená, že mezi těmito prvky neexistuje taková sekvence, která existuje v lineární datové struktuře.
Srovnávací graf
| Základ pro srovnání | Strom | Graf |
|---|---|---|
| Cesta | Pouze jeden mezi dvěma vrcholy. | Je povolena více než jedna cesta. |
| 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ší srovnatelně |
| Traversální techniky | Předobjednávka, objednávka a objednávka. | Vyhledávání první a první hloubky. |
| Počet hran | n-1 (kde n je počet uzlů) | Není definovaný |
| Typ modelu | Hierarchický | Síť |
Definice stromu
Strom je konečná kolekce datových položek obvykle označovaných jako 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 poboček, které tyto informace souvisejí. Přidání nové hrany do 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, binární strom se závitem, strom B, atd. Komprese dat, ukládání souborů, manipulace s aritmetickým výrazem a herními stromy jsou některé z aplikací stromu. datová struktura.
Vlastnosti stromu:
- Nahoře je strom označený jako kořen stromu.
- Zbývající datové položky jsou rozděleny do nesouvislých podmnožin, které se označují jako podstrom.
- Strom se rozšiřuje do výšky směrem dolů.
- Musí být připojen strom, což znamená, že musí existovat cesta z jednoho kořene do všech ostatních uzlů.
- Neobsahuje žádné smyčky.
- Strom má n-1 hrany.
Existují různé termíny spojené se stromy, jako je koncový uzel, hrana, úroveň, stupeň, hloubka, les atd. Mezi těmito termíny jsou některé z nich popsány níže.
- Edge - Linka, která spojuje 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 a tak dále až po terminál nebo listový uzel.
- Stupeň - Jedná se o počet podstromů uzlu v daném stromu.
- Hloubka - Je to maximální úroveň libovolného uzlu v daném stromu a také známá jako výška .
- Terminálový uzel - uzel nejvyšší úrovně je terminálový uzel, zatímco jiné uzly kromě terminálu a kořenového uzlu jsou označovány jako nekoncové terminály.
Definice grafu
Graf je také matematická nelineární datová struktura, která může reprezentovat různé druhy fyzické struktury. Skládá se ze skupiny vrcholů (nebo uzlů) a sady hran, které spojují dva vrcholy. Svislé body v grafu jsou znázorněny jako body nebo kruhy a hrany jsou zobrazeny jako oblouky nebo úsečky. Hrana je reprezentována E (v, w) kde v a w jsou páry vrcholů. Odstranění hrany z obvodu nebo připojeného grafu vytvoří subgraf, který je strom.
Grafy jsou rozděleny do různých kategorií, jako jsou řízené, neřízené, propojené, nepřipojené, jednoduché a více grafy. Počítačová síť, dopravní systém, graf sociální sítě, elektrické obvody a projektové plánování jsou některé z aplikací datové struktury grafů. Využívá se také v řídicí technice nazvané PERT (programová evaluační a revizní technika) a CPM (metoda kritické cesty), ve které je analyzována struktura grafu.
Vlastnosti grafu:
- Vrchol v grafu může být připojen k libovolnému počtu jiných vrcholů pomocí hran.
- Okraj může být směrován nebo směrován.
- Hranu lze vážit.
V grafu také používáme různé pojmy jako sousední vrcholy, cesta, cyklus, stupeň, připojený graf, kompletní graf, vážený graf, atd. Rozumíme některým z těchto termínů.
- Sousední vrcholy - Vrchol a je přilehlý k vrcholu b jestliže tam je okraj (a, b) nebo (b, a).
- Cesta - Cesta z náhodného vrcholu w je sousední posloupnost vrcholů.
- Cyklus - Je to cesta, kde jsou první a poslední vrcholy stejné.
- Stupeň - Jedná se o počet hran dopadajících na vrchol.
- Připojený graf - Pokud existuje cesta z náhodného vrcholu k jinému vrcholu, pak je tento graf známý jako připojený graf.
Klíčové rozdíly mezi stromem a grafem
- 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.
- Ve stromu je přesně jeden kořenový uzel a každé dítě může mít pouze jednoho rodiče. V grafu neexistuje žádný koncept kořenového uzlu.
- Strom nemůže mít smyčky a smyčky, zatímco graf může mít smyčky a smyčky.
- Grafy jsou složitější, protože mohou mít smyčky a smyčky. Naopak stromy jsou oproti grafu jednoduché.
- Strom je projížděn technikami předobjednávky, v pořadí a po objednávce. Na druhou stranu, pro přechod grafů používáme BFS (Breadth First Search) a DFS (Depth First Search).
- Strom může mít n-1 hrany. Naopak v grafu neexistuje žádný předem definovaný počet hran a záleží na grafu.
- Strom má hierarchickou strukturu, zatímco graf má model sítě.
Závěr
Graf a strom jsou nelineární datové struktury, které slouží k řešení různých složitých problémů. Graf je skupina vrcholů a hran, kde hrana spojuje pár vrcholů, zatímco strom je považován za minimálně připojený graf, který musí být připojen a nesmí být smyčky.
