Rozdiel medzi stromom a grafom
Obsah
Strom a graf spadajú 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 sieťový model. Strom a graf sú rozlíšené skutočnosťou, že stromová štruktúra musí byť spojená a nikdy nemôže mať slučky, zatiaľ čo v grafe takéto obmedzenia neexistujú.
Nelineárna dátová štruktúra pozostáva zo súboru prvkov, ktoré sú rozmiestnené v rovine, čo znamená, že medzi prvkami neexistuje taká sekvencia, ako existuje v lineárnej dátovej štruktúre.
-
- Porovnávacia tabuľka
- definícia
- Kľúčové rozdiely
- záver
Porovnávacia tabuľka
| Základ pre porovnanie | strom | graf |
|---|---|---|
| cesta | Iba jeden z dvoch vrcholov. | Je povolených viac ako jedna cesta. |
| Koreňový uzol | Má presne jeden koreňový uzol. | Graf nemá koreňový uzol. |
| Loops | Nie sú povolené žiadne slučky. | Graf môže mať slučky. |
| zložitosť | Menej zložité | Komplexnejšie porovnateľne |
| Techniky kríženia | Predobjednávka, objednávka a objednávka. | Prvé vyhľadávanie v šírke a prvé vyhľadávanie v hĺbke. |
| Počet hrán | n-1 (kde n je počet uzlov) | Neurčené |
| Typ modelu | hierarchický | sieť |
Definícia stromu
strom je konečná zbierka dátových položiek, ktoré sa zvyčajne nazývajú uzly. Ako je uvedené vyššie, strom je nelineárna dátová štruktúra, ktorá usporiadáva údajové položky v zoradenom poradí. Používa sa na znázornenie hierarchickej štruktúry medzi rôznymi dátovými prvkami a usporiadanie údajov do vetiev, ktoré sa týkajú informácií. Pridanie novej hrany do stromu vedie k vytvoreniu slučky alebo obvodu.
Existuje niekoľko druhov stromov, ako napríklad binárny strom, binárny vyhľadávací strom, strom AVL, vláknitý binárny strom, strom B atď. Kompresia údajov, ukladanie súborov, manipulácia s aritmetickým výrazom a stromami hier sú niektoré z aplikácií stromu. dátová štruktúra.
Vlastnosti stromu:
- V hornej časti stromu je označený uzol známy ako koreň stromu.
- Zostávajúce údajové položky sú rozdelené do disjunktných podmnožín, ktoré sa označujú ako podstrom.
- Strom sa na výšku rozširuje smerom dole.
- Musí byť pripojený strom, čo znamená, že musí existovať cesta od jedného koreňa k všetkým ostatným uzlom.
- Neobsahuje slučky.
- Strom má okraje n-1.
K stromom sú spojené rôzne výrazy, ako napríklad koncový uzol, hrana, úroveň, stupeň, hĺbka, les atď. Medzi týmito výrazmi sú niektoré z nich popísané nižšie.
- Hrana - Linka spájajúca dva uzly.
- hladina - Strom je rozdelený do úrovní tak, že koreňový uzol je na úrovni 0. Potom sú jeho najbližšie deti na úrovni 1 a jeho najbližšie deti sú na úrovni 2 a tak ďalej až do koncového alebo listového uzla.
- stupeň - Je to počet podstromov uzla v danom strome.
- hĺbka - Je to maximálna úroveň ktoréhokoľvek uzla v danom strome a tiež známa ako výška.
- Koncový uzol - Uzol najvyššej úrovne je terminálový uzol, zatiaľ čo iné uzly s výnimkou terminálového a koreňového uzla sú známe ako nekoncové uzly.
Definícia grafu
graf je tiež matematická nelineárna dátová štruktúra, ktorá môže predstavovať rôzne druhy fyzikálnej štruktúry. Skladá sa zo skupiny vrcholov (alebo uzlov) a sady hrán, ktoré spájajú tieto dva vrcholy. Vrcholy na grafe sú znázornené ako bod alebo kružnice a hrany sú zobrazené ako oblúky alebo úsečky. Hranu predstavuje E (v, w), kde v a w sú páry vrcholov. Odstránením okraja z obvodu alebo pripojeného grafu sa vytvorí podgraf, ktorým je strom.
Grafy sú rozdelené do rôznych kategórií, ako sú riadené, nesmerované, spojené, nepripojené, jednoduché a viacgrafové. Počítačová sieť, dopravný systém, graf sociálnych sietí, elektrické obvody a projektové plánovanie sú niektoré z aplikácií štruktúry grafových dát. Používa sa aj v technike riadenia s názvom PERT (metóda hodnotenia a preskúmania programu) a CPM (metóda kritickej cesty), v ktorej sa analyzuje štruktúra grafu.
Vlastnosti grafu:
- Vrchol v grafe môže byť spojený s ľubovoľným počtom ďalších vrcholov pomocou hrán.
- Okraj môže byť presmerovaný alebo nasmerovaný.
- Hranu je možné vážiť.
V grafe tiež používame rôzne výrazy, ako sú susedné vrcholy, cesta, cyklus, stupeň, pripojený graf, kompletný graf, vážený graf atď. Pochopme niektoré z týchto výrazov.
- Susedné vrcholy - Vrchol a je priľahlý k vrcholu b, ak je hrana (a, b) alebo (b, a).
- cesta - Cesta z náhodného vrcholu w je susednou sekvenciou vrcholov.
- cyklus - Je to cesta, kde prvý a posledný vrchol sú rovnaké.
- stupeň - Ide o niekoľko hrán dopadajúcich na vrchol.
- Pripojený graf - Ak existuje cesta z náhodného vrcholu do iného vrcholu, potom sa tento graf nazýva pripojený graf.
- V strome existuje iba jedna cesta medzi ľubovoľnými dvoma vrcholmi, zatiaľ čo graf môže mať jednosmerné a obojsmerné cesty medzi uzlami.
- V strome je presne jeden koreňový uzol a každé dieťa môže mať iba jedného rodiča. Na rozdiel od toho v grafe neexistuje koncepcia koreňového uzla.
- Strom nemôže mať slučky a slučky, graf môže mať slučky a slučky.
- Grafy sú zložitejšie, pretože môžu obsahovať slučky a slučky. Na rozdiel od toho sú stromy v porovnaní s grafom jednoduché.
- Strom sa prechádza technikami predobjednávky, poradia a poradia. Na druhú stranu, pre priechod grafu používame BFS (Breadth First Search) a DFS (Depth First Search).
- Strom môže mať okraje n-1. Naopak, v grafe nie je vopred určený počet hrán a záleží to na grafe.
- Strom má hierarchickú štruktúru, zatiaľ čo graf má sieťový model.
záver
Graf a strom sú nelineárne dátové štruktúry, ktoré sa používajú na riešenie rôznych zložitých problémov. Graf je skupina vrcholov a hrán, kde hrana spája dvojicu vrcholov, zatiaľ čo strom sa považuje za minimálne pripojený graf, ktorý musí byť spojený a bez slučiek.
