Skillnaden Mellan Graf Och Träd

2024 Författare: Mildred Bawerman | [email protected]. Senast ändrad: 2023-12-16 08:42

Diagram mot träd

Graf och träd används i datastrukturer. Det finns verkligen vissa skillnader mellan diagram och träd. En uppsättning hörn som har en binär relation kallas ett diagram medan träd är en datastruktur som har en uppsättning noder kopplade till varandra.

Graf

En graf är en uppsättning objekt som är förbundna med kanter och varje objekt kallas nod eller toppunkt. Med andra ord kan en graf definieras som uppsättningen av hörn och det finns en binär relation mellan dessa hörn.

Vid implementering av ett diagram implementeras noderna som objekt eller strukturer. Kanterna kan representeras på olika sätt. Ett av sätten är att varje nod kan associeras med en incident-edge array. Om informationen ska lagras i noder snarare än kanter fungerar matriserna som pekare till noder och representerar också kanter. En av fördelarna med detta tillvägagångssätt är att ytterligare noder kan läggas till i diagrammet. Befintliga noder kan anslutas genom att lägga till element i matriser. Men det finns en nackdel eftersom det krävs tid för att avgöra om det finns en kant mellan noderna.

Ett annat sätt att göra detta är att behålla en tvådimensionell matris eller matris M som har booleska värden. Förekomsten av kant från nod i till j specificeras av posten Mij. En av fördelarna med denna metod är att ta reda på om det finns någon kant mellan två noder.

Träd

Tree är också en datastruktur som används inom datavetenskap. Det liknar trädets struktur och har en uppsättning noder som är länkade till varandra.

En nod i ett träd kan innehålla ett villkor eller värde. Det kan också vara ett eget träd eller det kan representera en separat datastruktur. Noll eller flera noder finns i en trädatastruktur. Om en nod har ett barn kallas det föräldernod för det barnet. Det kan vara högst en förälder till en nod. Den längsta vägen nedåt från noden till ett blad är nodens höjd. Djupet på noden representeras av sökvägen till dess rot.

I ett träd kallas den översta noden rotnod. Rotnoden har inga föräldrar eftersom den är den högsta. Från denna nod börjar alla trädoperationer. Genom att använda länkar eller kanter kan andra noder nås från rotnoden. Noder längst ner kallas bladnoder och de har inga barn. Den nod som har antal underordnade noder kallas inre nod eller intern nod.

• Ett träd kan beskrivas som ett specialfall av diagram utan självslingor och kretsar.

• Det finns inga öglor i ett träd medan en graf kan ha öglor.

• Det finns tre uppsättningar i en graf, dvs. kanter, hörn och en uppsättning som representerar deras relation medan ett träd består av noder som är kopplade till varandra. Dessa anslutningar kallas kanter.

• I trädet finns det många regler som stavar hur anslutningar av noder kan uppstå medan grafen inte har några regler som dikterar anslutningen mellan noder.