Inhoud

• Vergelijkingstabel
• Definitie van boom
• Eigenschappen van boom:
• Definitie van grafiek
• Eigenschappen van een grafiek:
• Gevolgtrekking

Boom en grafiek vallen onder de categorie niet-lineaire gegevensstructuur, waarbij boom een ​​zeer nuttige manier is om een ​​relatie tussen de knooppunten in een hiërarchische structuur weer te geven en de grafiek een netwerkmodel volgt. Boom en grafiek onderscheiden zich door het feit dat een boomstructuur moet worden verbonden en nooit lussen mag hebben, terwijl er in de grafiek dergelijke beperkingen niet zijn.

Een niet-lineaire gegevensstructuur bestaat uit een verzameling elementen die op een vlak zijn verdeeld, wat betekent dat er geen volgorde tussen de elementen bestaat zoals deze bestaat in een lineaire gegevensstructuur.

1. 1. Vergelijkingstabel
   2. Definitie
   3. Belangrijkste verschillen
   4. Gevolgtrekking

Vergelijkingstabel

Basis voor vergelijking	Boom	diagram
Pad	Slechts één tussen twee hoekpunten.	Meer dan één pad is toegestaan.
Wortelknooppunt	Het heeft precies één root-knooppunt.	Grafiek heeft geen root-knooppunt.
Loops	Lussen zijn niet toegestaan.	Grafiek kan lussen hebben.
ingewikkeldheid	Minder complex	In vergelijking complexer
Traversale technieken	Pre-order, In-order en Post-order.	Breedte-eerste zoekopdracht en diepte-eerste zoekopdracht.
Aantal randen	n-1 (waarbij n het aantal knooppunten is)	Niet gedefinieerd
Model type	hiërarchische	Netwerk

Definitie van boom

EEN boom is een eindige verzameling gegevensitems die meestal knooppunten worden genoemd. Zoals hierboven vermeld, is een boom een ​​niet-lineaire gegevensstructuur die gegevensitems in gesorteerde volgorde rangschikt. Het wordt gebruikt om een ​​hiërarchische structuur tussen de verschillende gegevenselementen weer te geven en organiseert de gegevens in takken die de informatie relateren. De toevoeging van een nieuwe rand in een boom resulteert in een vorming van de lus of het circuit.

Er zijn verschillende soorten bomen, zoals een binaire boom, binaire zoekboom, AVL-boom, threaded binaire boom, B-boom, etc. Datacompressie, bestandsopslag, manipulatie van de rekenkundige uitdrukking en spelbomen zijn enkele van de toepassingen van boom data structuur.

Eigenschappen van boom:

• Er is een knooppunt aan de bovenkant van de boom, bekend als een wortel van de boom.
• De resterende gegevensitems zijn onderverdeeld in onsamenhangende subsets die worden aangeduid als subtree.
• De boom is in hoogte naar beneden toe uitgezet.
• Een boom moet worden verbonden, wat betekent dat er een pad moet zijn van de ene wortel naar alle andere knooppunten.
• Het bevat geen lussen.
• Een boom heeft n-1 randen.

Er zijn verschillende termen geassocieerd met bomen zoals eindknooppunt, rand, niveau, graad, diepte, bos, etc. Onder deze termen, sommige van hen hieronder beschreven.

• Rand - Een lijn die twee knooppunten verbindt.
• Niveau - Een boom is opgedeeld in niveaus zodat de wortelknoop zich op niveau 0 bevindt. De directe kinderen bevinden zich dan op niveau 1 en de directe kinderen bevinden zich op niveau 2 enzovoort tot aan de terminal of de bladknoop.
• Mate - Het is het aantal substructuren van een knooppunt in een bepaalde boom.
• Diepte - Het is het maximale niveau van een knooppunt in een bepaalde boom en ook bekend als hoogte.
• Terminal knooppunt - Het knooppunt op het hoogste niveau is terminalknooppunt, terwijl andere knooppunten behalve terminal- en rootknooppunt niet-terminale knooppunten worden genoemd.

Definitie van grafiek

EEN diagram is ook een wiskundige niet-lineaire gegevensstructuur die verschillende soorten fysieke structuren kan vertegenwoordigen. Het bestaat uit een groep hoekpunten (of knopen) en een reeks randen die de twee hoekpunten verbinden. Hoekpunten op de grafiek worden weergegeven als punt of cirkels en randen worden weergegeven als bogen of lijnsegmenten. Een rand wordt voorgesteld door E (v, w) waarbij v en w de paren hoekpunten zijn. Als een rand uit een circuit of een verbonden grafiek wordt verwijderd, wordt een subafbeelding gemaakt die een boom is.

De grafieken zijn onderverdeeld in verschillende categorieën, zoals gericht, niet-gericht, verbonden, niet-verbonden, eenvoudig en met meerdere grafieken. Computernetwerk, transportsysteem, sociale netwerkgrafiek, elektrische circuits en projectplanning zijn enkele van de toepassingen van grafische gegevensstructuur. Het wordt ook gebruikt in managementtechniek genoemd als PERT (programma-evaluatie en beoordelingstechniek) en CPM (kritieke padmethode) waarin de grafiekstructuur wordt geanalyseerd.

Eigenschappen van een grafiek:

• Een hoekpunt in een grafiek kan met randen worden verbonden met een willekeurig aantal andere hoekpunten.
• Een edge kan worden doorgestuurd of gericht.
• Een rand kan worden gewogen.

In grafiek gebruiken we ook verschillende termen zoals aangrenzende hoekpunten, pad, cyclus, graad, verbonden grafiek, complete grafiek, gewogen grafiek, enz. Laten we enkele van deze termen begrijpen.

• Aangrenzende hoekpunten - Een hoekpunt a grenst aan hoekpunt b als er een rand (a, b) of (b, a) is.
• Pad - Een pad van een willekeurig hoekpunt w is een aangrenzende reeks hoekpunten.
• Fiets - Het is een pad waar de eerste en laatste hoekpunten hetzelfde zijn.
• Mate - Het is een aantal randen dat op een hoekpunt invalt.
• Verbonden grafiek - Als er een pad bestaat van een willekeurig hoekpunt naar een ander hoekpunt, staat die grafiek bekend als een verbonden grafiek.

1. In een boom bestaat er slechts één pad tussen twee hoekpunten, terwijl een grafiek unidirectionele en bidirectionele paden tussen de knooppunten kan hebben.
2. In de boom is er precies één root-knooppunt en elk kind kan slechts één ouder hebben. In tegenstelling tot een grafiek is er geen concept van het root-knooppunt.
3. Een boom kan geen lussen en zelflussen hebben, terwijl de grafiek lussen en zelflussen kan hebben.
4. Grafieken zijn ingewikkelder omdat het lussen en zelflussen kan hebben. Bomen zijn daarentegen eenvoudig in vergelijking met de grafiek.
5. De boom wordt doorkruist met behulp van pre-order, in-order en post-order technieken. Aan de andere kant gebruiken we voor grafiekverplaatsing BFS (Breadth First Search) en DFS (Depth First Search).
6. Een boom kan n-1 randen hebben. Integendeel, in de grafiek is er geen vooraf gedefinieerd aantal randen en dit hangt af van de grafiek.
7. Een boom heeft een hiërarchische structuur, terwijl de grafiek een netwerkmodel heeft.

Gevolgtrekking

Grafiek en structuur zijn de niet-lineaire gegevensstructuur die wordt gebruikt om verschillende complexe problemen op te lossen. Een grafiek is een groep hoekpunten en randen waarbij een rand een paar hoekpunten verbindt, terwijl een boom wordt beschouwd als een minimaal verbonden grafiek die moet worden verbonden en vrij van lussen.