Graph vs Tree
Graph och Tree används i datastrukturer. Det finns säkert vissa skillnader mellan Graph och Tree. En uppsättning hörn som har en binär relation kallas en graf medan träd är en datastruktur som har en uppsättning noder kopplade till varandra.
Graph
En graf är en uppsättning objekt som är sammankopplade med kanter och varje objekt kallas nod eller vertex. Med andra ord kan en graf definieras som uppsättningen av hörn och det finns en binär relation mellan dessa hörn.
I implementering av en graf 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 infallande kantmatris. Om informationen ska lagras i noder snarare än kanter så fungerar arrayerna som pekare till noder och representerar även kanter. En av fördelarna med detta tillvägagångssätt är att ytterligare noder kan läggas till grafen. Befintliga noder kan anslutas genom att lägga till element i arrayer. 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 inmatningen Mij. En av fördelarna med denna metod är att ta reda på om det finns någon kant mellan två noder.
Träd
Träd ä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 representera en separat datastruktur. Noll eller fler noder finns i en träddatastruktur. Om en nod har ett barn kallas det föräldranod för det barnet. Det kan vara högst en förälder till en nod. Den längsta nedåtgående vägen från noden till ett löv är nodens höjd. Nodens djup 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 översta. 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. De lägsta nivånoderna kallas lövnoder och de har inga barn. Noden som har antalet underordnade noder kallas inre nod eller intern nod.
Skillnad mellan graf och träd:
• Ett träd kan beskrivas som ett specialiserat fall av graf utan självslingor och kretsar.
• Det finns inga loopar i ett träd medan en graf kan ha loopar.
• 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 beskriver hur anslutningar av noder kan ske medan grafen inte har några regler som dikterar kopplingen mellan noderna.
