Verschil tussen grafiek en boom

Graph versus Tree

Graph en Tree worden gebruikt in datastructuren. Er zijn zeker enkele verschillen tussen Graph en Tree. Een set hoekpunten met een binaire relatie wordt een grafiek genoemd, terwijl boom een ​​gegevensstructuur is met een reeks knooppunten die aan elkaar zijn gekoppeld.

diagram

Een grafiek is een reeks items die zijn verbonden door randen en elk item staat bekend als knooppunt of vertex. Met andere woorden, een grafiek kan worden gedefinieerd als de verzameling hoekpunten en er is een binaire relatie tussen deze hoekpunten.

Bij de implementatie van een grafiek worden de knooppunten geïmplementeerd als objecten of structuren. De randen kunnen op verschillende manieren worden weergegeven. Een van de manieren is dat elk knooppunt kan worden geassocieerd met een array met incidentranden. Als de informatie moet worden opgeslagen in knooppunten in plaats van randen, fungeren de arrays als verwijzingen naar knooppunten en ook als randen. Een van de voordelen van deze aanpak is dat er extra knooppunten aan de grafiek kunnen worden toegevoegd. Bestaande knooppunten kunnen worden verbonden door elementen aan arrays toe te voegen. Maar er is een nadeel omdat tijd nodig is om te bepalen of er een rand is tussen de knooppunten.

Een andere manier om dit te doen is om een ​​tweedimensionale matrix of matrix M te behouden met Booleaanse waarden. Het bestaan ​​van rand vanaf knooppunt i tot j wordt gespecificeerd door invoer Mij. Een van de voordelen van deze methode is om uit te zoeken of er een grens is tussen twee knooppunten.

Boom

Tree is ook een datastructuur die wordt gebruikt in de informatica. Het is vergelijkbaar met de structuur van de boom en heeft een set knooppunten die aan elkaar zijn gekoppeld.

Een knooppunt van een boom kan een toestand of waarde bevatten. Het kan ook een eigen boom zijn of het kan een afzonderlijke gegevensstructuur vertegenwoordigen. Nul of meer knooppunten zijn aanwezig in een boomgegevensstructuur. Als een knooppunt een kind heeft, wordt dit het bovenliggende knooppunt van dat kind genoemd. Er kan maximaal één ouder van een knooppunt zijn. Het langste neerwaartse pad van het knooppunt naar een blad is de hoogte van het knooppunt. De diepte van het knooppunt wordt weergegeven door het pad naar de hoofdmap.

In een boom wordt het bovenste knooppunt het hoofdknooppunt genoemd. Het basisknooppunt heeft geen ouders omdat dit het bovenste is. Vanaf dit knooppunt beginnen alle boombewerkingen. Door koppelingen of randen te gebruiken, kunnen andere knooppunten worden bereikt vanaf het basisknooppunt. De knooppunten op het laagste niveau worden bladknooppunten genoemd en ze hebben geen kinderen. Het knooppunt met het aantal onderliggende knooppunten wordt genoemd innerlijke knooppunt of interne knooppunt.