Grafiek versus boom
Graph en Tree worden gebruikt in datastructuren. Er zijn zeker enkele verschillen tussen Graph en Tree. Een reeks hoekpunten met een binaire relatie wordt een grafiek genoemd, terwijl de boom een gegevensstructuur is met een reeks knooppunten die met elkaar zijn verbonden.
Grafiek
Een grafiek is een set items die met elkaar zijn verbonden door randen en elk item staat bekend als knooppunt of hoekpunt. Met andere woorden, een graaf kan worden gedefinieerd als de set hoekpunten en er is een binaire relatie tussen deze hoekpunten.
Bij 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 reeks invallende randen. Als de informatie moet worden opgeslagen in knooppunten in plaats van randen, fungeren de arrays als verwijzingen naar knooppunten en vertegenwoordigen ze ook randen. Een van de voordelen van deze benadering 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 één nadeel, omdat er tijd nodig is om te bepalen of er een rand tussen de knooppunten is.
Een andere manier om dit te doen, is door een tweedimensionale array of matrix M te behouden die Booleaanse waarden heeft. Het bestaan van een rand van knooppunt i tot j wordt gespecificeerd door de invoer Mij. Een van de voordelen van deze methode is om erachter te komen of er een rand is tussen twee knooppunten.
Boom
Tree is ook een datastructuur die wordt gebruikt in de informatica. Het lijkt op de structuur van de boom en heeft een reeks knooppunten die met elkaar zijn verbonden.
Een knooppunt van een boom kan een voorwaarde of waarde bevatten. Het kan ook een eigen boom zijn of het kan een aparte datastructuur vertegenwoordigen. Er zijn nul of meer knooppunten 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 pad naar beneden van het knooppunt naar een blad is de hoogte van het knooppunt. De diepte van het knooppunt wordt weergegeven door het pad naar de wortel.
In een boom wordt het bovenste knooppunt root-knooppunt genoemd. Het hoofdknooppunt heeft geen ouders omdat dit de bovenste is. Vanaf dit knooppunt beginnen alle boombewerkingen. Door links of randen te gebruiken, kunnen andere knooppunten worden bereikt vanaf het hoofdknooppunt. De onderste niveau-knooppunten worden bladknooppunten genoemd en ze hebben geen kinderen. Het knooppunt met een aantal onderliggende knooppunten wordt binnenknooppunt of intern knooppunt genoemd.
• Een boom kan worden omschreven als een gespecialiseerd geval van een grafiek zonder zelflussen en circuits.
• Er zijn geen lussen in een boom, terwijl een grafiek lussen kan hebben.
• Er zijn drie sets in een grafiek, dwz randen, hoekpunten en een set die hun relatie vertegenwoordigt, terwijl een boom bestaat uit knooppunten die met elkaar zijn verbonden. Deze verbindingen worden randen genoemd.
• In de boom zijn er talloze regels die beschrijven hoe verbindingen van knooppunten kunnen ontstaan, terwijl de grafiek geen regels heeft die de verbinding tussen de knooppunten dicteren.
