Doporučená, 2022

Redakce Choice

Rozdíl mezi stromem a grafem

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 následuje síťový model. Strom a graf se rozlišují tím, že stromová struktura musí být připojena a nikdy nemůže mít 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 těmito prvky neexistuje taková sekvence, která existuje v lineární datové struktuře.

Srovnávací graf

Základ pro srovnáníStromGraf
CestaPouze jeden mezi dvěma vrcholy.Je povolena více než jedna cesta.
Kořenový uzelMá přesně jeden kořenový uzel.Graf nemá kořenový uzel.
SmyčkyNejsou povoleny žádné smyčky.Graf může mít smyčky.
SložitostMéně složitéSložitější srovnatelně
Traversální technikyPředobjednávka, objednávka a objednávka.Vyhledávání první a první hloubky.
Počet hrann-1 (kde n je počet uzlů)Není definovaný
Typ modeluHierarchický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

  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. V grafu neexistuje žádný koncept kořenového uzlu.
  3. Strom nemůže mít smyčky a smyčky, zatímco graf může mít smyčky a smyčky.
  4. Grafy jsou složitější, protože mohou mít smyčky a smyčky. Naopak stromy jsou oproti grafu jednoduché.
  5. 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).
  6. Strom může mít n-1 hrany. Naopak v grafu neexistuje žádný předem definovaný počet hran a záleží na grafu.
  7. 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.

Top