Graph vs Tree
Graph og Tree bruges i datastrukturer. Der er bestemt nogle forskelle mellem Graph og Tree. Et sæt toppunkter med en binær relation kaldes en graf, hvorimod træ er en datastruktur, der har et sæt knudepunkter knyttet til hinanden.
Graph
En graf er et sæt elementer, der er forbundet med kanter, og hvert element er kendt som node eller toppunkt. Med andre ord kan en graf defineres som et sæt af toppunkter, og der er en binær relation mellem disse toppunkter.
I implementering af en graf implementeres noderne som objekter eller strukturer. Kanterne kan repræsenteres på forskellige måder. En af måderne er, at hver node kan associeres med en hændelseskant-array. Hvis informationen skal lagres i noder i stedet for kanter, fungerer arrays som pointere til noder og repræsenterer også kanter. En af fordelene ved denne tilgang er, at yderligere knudepunkter kan tilføjes til grafen. Eksisterende noder kan forbindes ved at tilføje elementer til arrays. Men der er én ulempe, fordi der kræves tid for at afgøre, om der er en kant mellem knudepunkterne.
En anden måde at gøre dette på er at beholde en todimensionel matrix eller matrix M, der har booleske værdier. Eksistensen af kant fra node i til j er specificeret ved indtastning Mij. En af fordelene ved denne metode er at finde ud af, om der er nogen kant mellem to noder.
Træ
Tree er også en datastruktur, der bruges i datalogi. Det ligner træets struktur og har et sæt knudepunkter, der er knyttet til hinanden.
En knude i et træ kan indeholde en betingelse eller værdi. Det kan også være et eget træ, eller det kan repræsentere en separat datastruktur. Der er nul eller flere noder i en trædatastruktur. Hvis en knude har et underordnet, kaldes det overordnet knude for det underordnede. Der kan højst være én forælder til en node. Den længste nedadgående vej fra noden til et blad er højden af noden. Dybden af noden er repræsenteret af stien til dens rod.
I et træ kaldes den øverste node rodknude. Rodnoden har ingen forældre, da den er den øverste. Fra denne node begynder alle træoperationer. Ved at bruge links eller kanter kan andre noder nås fra rodnoden. De nederste niveauknuder kaldes bladknuder, og de har ingen børn. Den node, der har antallet af underordnede noder, kaldes indre node eller intern node.
Forskel mellem graf og træ:
• Et træ kan beskrives som et specialiseret tilfælde af grafer uden selvsløjfer og kredsløb.
• Der er ingen sløjfer i et træ, hvorimod en graf kan have sløjfer.
• Der er tre sæt i en graf, dvs. kanter, hjørner og et sæt, der repræsenterer deres relation, mens et træ består af noder, der er forbundet med hinanden. Disse forbindelser omtales som kanter.
• I træet er der adskillige regler, der præciserer, hvordan forbindelser af noder kan opstå, mens grafen ikke har nogen regler, der dikterer forbindelsen mellem noderne.
