Rozdiel medzi stromom a grafom

2019

Strom a graf patria do kategórie nelineárnej dátovej štruktúry, kde strom ponúka veľmi užitočný spôsob reprezentácie vzťahu medzi uzlami v hierarchickej štruktúre a graf sleduje model siete. Strom a graf sú rozlíšené tým, že stromová štruktúra musí byť pripojená a nikdy nemôže mať slučky, zatiaľ čo v grafe nie sú žiadne také obmedzenia.

Nelineárna dátová štruktúra pozostáva zo zbierky prvkov, ktoré sú rozložené v rovine, čo znamená, že medzi prvkami nie je taká sekvencia, ako existuje v lineárnej dátovej štruktúre.

Porovnávacia tabuľka

Základ pre porovnanie	strom	graf
cesta	Len jeden medzi dvoma vrcholmi.	Je povolená viac ako jedna cesta.
Koreňový uzol	Má presne jeden koreňový uzol.	Graf nemá koreňový uzol.
Loops	Žiadne slučky nie sú povolené.	Graf môže mať slučky.
zložitosť	Menej zložité	Komplexnejšie
Traverzné techniky	Predobjednávka, In-order a Post-Order.	Vyhľadávanie v hĺbke a hĺbkové vyhľadávanie.
Počet okrajov	n-1 (kde n je počet uzlov)	Nie je definované
Typ modelu	hierarchický	sieť

Definícia stromu

Strom je konečná zbierka dátových položiek, zvyčajne označovaných ako uzly. Ako už bolo spomenuté vyššie, strom je nelineárna dátová štruktúra, ktorá usporadúva dáta v triedenom poradí. Používa sa na zobrazenie hierarchickej štruktúry medzi rôznymi dátovými prvkami a organizuje údaje do pobočiek, ktoré súvisia s informáciami. Pridanie novej hrany do stromu vedie k vytvoreniu slučky alebo obvodu.

Existuje niekoľko typov stromov, ako je binárny strom, binárny strom vyhľadávania, strom AVL, závitový binárny strom, B-strom atď. Kompresia dát, ukladanie súborov, manipulácia s aritmetickým výrazom a herné stromy sú niektoré aplikácie stromu dátová štruktúra.

Vlastnosti stromu:

V hornej časti stromu je označený uzol známy ako koreň stromu.
Zostávajúce položky údajov sú rozdelené na disjunktné podsúbory označené ako podstrom.
Strom sa rozširuje smerom dole.
Strom musí byť pripojený, čo znamená, že musí existovať cesta z jedného koreňa na všetky ostatné uzly.
Neobsahuje žiadne slučky.
Strom má hrany n-1.

Existujú rôzne pojmy spojené so stromami, ako je koncový uzol, okraj, úroveň, stupeň, hĺbka, lesy atď. Medzi týmito výrazmi sú niektoré z nich opísané nižšie.

Okraj - linka, ktorá spája dva uzly.
Stupeň - strom je rozdelený na úrovne tak, že koreňový uzol je na úrovni 0. Potom sú jeho bezprostredné deti na úrovni 1 a jeho bezprostredné deti sú na úrovni 2 a tak ďalej až do terminálu alebo uzla listov.
Titulok - Je to počet podstrán uzla v danom strome.
Hĺbka - je to maximálna úroveň akéhokoľvek uzla v danom strome a tiež známa ako výška .
Uzol terminálu - uzol najvyššej úrovne je uzol terminálu, zatiaľ čo ostatné uzly okrem terminálu a koreňového uzla sú známe ako neterminálne uzly.

Definícia grafu

Graf je tiež matematickou nelineárnou dátovou štruktúrou, ktorá môže predstavovať rôzne druhy fyzickej štruktúry. Pozostáva zo skupiny vrcholov (alebo uzlov) a množiny okrajov, ktoré spájajú oba vrcholy. Hrany na grafe sú reprezentované ako bod alebo kruhy a hrany sú zobrazené ako oblúky alebo segmenty riadkov. Hrana predstavuje E (v, w), kde v a w sú dvojice vrcholov. Odstránenie okraja z obvodu alebo pripojeného grafu vytvára subgraf, ktorý je strom.

Grafy sú rozdelené do rôznych kategórií, ako sú usmerňované, nesmerované, prepojené, nepripojené, jednoduché a viacgrafové. Počítačová sieť, dopravný systém, graf sociálnych sietí, elektrické obvody a plánovanie projektov sú niektoré aplikácie grafovej štruktúry dát. Používa sa tiež v riadiacej technike pomenovanej ako PERT (technika hodnotenia a hodnotenia programu) a metóda CPM (kritická cesta), v ktorej sa analyzuje štruktúra grafu.

Vlastnosti grafu:

Vrchol v grafe môže byť spojený s ľubovoľným počtom iných vrcholov pomocou okrajov.
Hrana môže byť smerované alebo nasmerované.
Hrana môže byť vážené.

V grafe tiež používame rôzne pojmy, ako sú priľahlé vrcholy, cesta, cyklus, stupeň, pripojený graf, kompletný graf, vážený graf atď. Poďme porozumieť niektorým z týchto výrazov.

Priľahlé vrcholy - vrchol a je vedľa vrcholu b, ak existuje hrana (a, b) alebo (b, a).
Cesta - cesta z náhodného vrcholu w je susediacou sekvenciou vrcholov.
Cyklus - Ide o cestu, kde sú prvé a posledné vrcholy rovnaké.
Stupeň - Je to veľa okrajov, ktoré dopadajú na vrchol.
Pripojený graf - Ak existuje cesta z náhodného vrcholu na akýkoľvek iný vrchol, potom tento graf je známy ako pripojený graf.

Kľúčové rozdiely medzi stromom a grafom

Vo stromu existuje iba jedna cesta medzi dvoma vrcholmi, zatiaľ čo graf môže mať jednosmerné a obojsmerné cesty medzi uzlami.
V strome existuje presne jeden koreňový uzol a každé dieťa môže mať len jedného rodiča. Oproti tomu v grafe neexistuje koncept koreňového uzla.
Strom nemôže mať slučky a samočinné slučky, zatiaľ čo graf môže mať slučky a samočinné slučky.
Grafy sú zložitejšie, pretože môžu mať slučky a samočinné slučky. Naproti tomu stromy sú v porovnaní s grafom jednoduché.
Strom prechádza technikami vopred objednanými, v poradí a po objednávke. Na druhej strane, pre traverzovanie grafov používame BFS (Breadth First Search) a DFS (Depth First Search).
Strom môže mať hrany n-1. Naopak, v grafe neexistuje preddefinovaný počet okrajov a záleží od grafu.
Strom má hierarchickú štruktúru, zatiaľ čo graf má sieťový model.

záver

Graf a strom sú nelineárna dátová štruktúra, ktorá sa používa na riešenie rôznych zložitých problémov. Graf je skupina vrcholov a okrajov, kde okraj spája pár vrcholov, zatiaľ čo strom je považovaný za minimálne pripojený graf, ktorý musí byť pripojený a bez slučiek.