Forskel mellem graf og træ

Anonim

Graf vs Træ

Graf og træ bruges i datastrukturer. Der er sikkert nogle forskelle mellem graf og træ. Et sæt af hjørner, der har et binært forhold, kaldes en graf, hvorimod træet er en datastruktur, der har et sæt knudepunkter forbundet med hinanden.

Graf

En graf er et sæt elementer, der er forbundet med kanter, og hvert element er kendt som knudepunkt eller vertex. Med andre ord kan en graf defineres som sæt af hjørner, og der er et binært forhold mellem disse hjørner.

Ved gennemførelse 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 forbindes med en indfaldskantergruppe. Hvis oplysningerne skal lagres i noder snarere end kanter, fungerer arrays som peger til knuder og repræsenterer også kanter. En af fordelene ved denne tilgang er, at yderligere noder kan tilføjes til grafen. Eksisterende noder kan forbindes ved at tilføje elementer til arrays. Men der er en ulempe, fordi tiden er nødvendig for at afgøre, om der er en kant mellem knuderne.

En anden måde at gøre dette på er at holde en todimensionel matrix eller matrix M, der har boolske værdier. Eksistensen af ​​kanten fra knudepunktet i til j er angivet ved indtastning Mij. En af fordelene ved denne metode er at finde ud af om der er nogen kant mellem to noder.

Træ

Træ er også en datastruktur, der anvendes i datalogi. Det ligner træets struktur og har et sæt noder, der er forbundet med hinanden.

En knude på et træ kan indeholde en tilstand 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 trædatastruktur. Hvis en knude har et barn, så kaldes det forælderens knudepunkt. Der kan højst være en forælder til en node. Den længste nedadgående vej fra knuden til et blad er knudehøjden. Dybden af ​​knudepunkt er repræsenteret af stien til dens rod.

I et træ kaldes den øverste node root node. Rotenoden har ingen forældre, da det er toppen mest. Fra denne knude begynder alle træoperationer. Ved at bruge links eller kanter kan andre knuder nås fra rodknuden. De nederste niveaender knytter sig til bladknudepunkter, og de har ingen børn. Den knude, der har antal barnnoter, kaldes indre node eller intern knudepunkt.

Forskel mellem graf og træ:

• Et træ kan beskrives som et specialiseret tilfælde af graf uden selvløkker 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 i. e. 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æ er der talrige regler, der stavar ud, hvordan forbindelser af noder kan forekomme, mens grafen ikke har nogen regler, der dikterer forbindelsen mellem knuderne.