Forskellen Mellem Graf Og Træ

2024 Forfatter: Mildred Bawerman | [email protected]. Sidst ændret: 2023-12-16 08:37

Graf vs træ

Graf og træ bruges i datastrukturer. Der er bestemt nogle forskelle mellem graf og træ. Et sæt hjørner med en binær relation kaldes en graf, mens træ er en datastruktur, der har et sæt noder, der er knyttet til hinanden.

Kurve

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 sæt af hjørner, og der er en binær relation mellem disse hjørner.

Ved 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 knude kan associeres med et hændende kanter-array. Hvis oplysningerne skal gemmes i noder snarere end kanter, fungerer arrays som peger på noder og repræsenterer også kanter. En af fordelene ved denne tilgang er, at yderligere noder kan føjes til grafen. Eksisterende noder kan forbindes ved at tilføje elementer til arrays. Men der er en ulempe, fordi der kræves tid til at bestemme, om der er en kant mellem noderne.

En anden måde at gøre dette på er at beholde et todimensionelt array eller matrix M, der har boolske værdier. Eksistensen af kant fra node i til j er specificeret ved post 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 anvendes inden for datalogi. Det svarer til træets struktur og har et sæt noder, der er knyttet til hinanden.

En node 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. Nul eller flere noder er til stede i en treddatastruktur. Hvis en knude har et barn, kaldes det forælderknude for det barn. Der kan højst være en forælder til en node. Den længste sti nedad fra knudepunktet til et blad er knudepunktets højde. Dybden af noden er repræsenteret af stien til dens rod.

I et træ kaldes den øverste knude rodknude. Rodknuden har ingen forældre, da den er den øverste mest. Fra denne knude begynder alle træoperationer. Ved at bruge links eller kanter kan andre noder nås fra rodnoden. Knuderne på det nederste niveau kaldes bladnoder, og de har ingen børn. Den node, der har antallet af underordnede noder, kaldes indre node eller intern node.

• Et træ kan beskrives som et specielt tilfælde af graf uden selvløkker og kredsløb.

• Der er ingen sløjfer i et træ, mens 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 kaldes kanter.

• I træet er der adskillige regler, der angiver, hvordan forbindelser af noder kan forekomme, mens grafen ikke har nogen regler, der dikterer forbindelsen mellem noder.