Innehåll

• Jämförelsediagram
• Definition av träd
• Egenskaper hos träd:
• Definition av graf
• Egenskaper för en graf:
• Slutsats

Träd och diagram ingår i kategorin icke-linjär datastruktur där träd erbjuder ett mycket användbart sätt att representera ett samband mellan noderna i en hierarkisk struktur och graf följer en nätverksmodell. Träd och diagram är differentierade av det faktum att en trädstruktur måste vara ansluten och aldrig kan ha slingor medan det i grafen inte finns några sådana begränsningar.

En icke-linjär datastruktur består av en samling av elementen som är fördelade på ett plan vilket innebär att det inte finns någon sådan sekvens mellan elementen som de finns i en linjär datastruktur.

1. 1. Jämförelsediagram
   2. Definition
   3. Viktiga skillnader
   4. Slutsats

Jämförelsediagram

Grund för jämförelse	Träd	Graf
Väg	Endast en mellan två toppar.	Mer än en sökväg är tillåten.
Rotknut	Den har exakt en rotnod.	Grafen har inte en rotnod.
Loops	Inga öglor är tillåtna.	Graf kan ha öglor.
Komplexitet	Mindre komplex	Mer komplex jämförelsevis
Traversal tekniker	Förbeställning, beställning och efterbeställning.	Bredd-första sökning och djup-första sökning.
Antal kanter	n-1 (där n är antalet noder)	Inte definierad
Modell typ	Hierarkisk	Nätverk

Definition av träd

EN träd är en ändlig samling av dataobjekt som vanligtvis benämns noder. Som nämnts ovan är att ett träd är en icke-linjär datastruktur som ordnar dataobjekt i sorterad ordning. Den används för att visa en hierarkisk struktur mellan de olika dataelementen och organiserar data i grenar som relaterar informationen. Tillsatsen av en ny kant i ett träd resulterar i en bildning av slingan eller kretsen.

Det finns flera typer av träd som ett binärt träd, binärt sökträd, AVL-träd, gängat binärt träd, B-träd etc. Datakomprimering, fillagring, manipulation av det aritmetiska uttrycket och spelträd är några av tillämpningarna av träd datastruktur.

Egenskaper hos träd:

• Det är betecknad nod på toppen av trädet som kallas en rotrot.
• De återstående dataelementen är indelade i osammanhängande delmängder som kallas undertråd.
• Trädet expanderas i höjd mot botten.
• Ett träd måste anslutas vilket innebär att det måste finnas en väg från en rot till alla andra noder.
• Det innehåller inga slingor.
• Ett träd har n-1 kanter.

Det finns olika termer förknippade med träd som terminalnod, kant, nivå, grad, djup, skog etc. Bland dessa termer beskrivs några av dem nedan.

• Kant - En linje som ansluter två noder.
• Nivå - Ett träd är indelat i nivåer så att rotnoden är på nivå 0. Då är dess omedelbara barn på nivå 1, och dess omedelbara barn är på nivå 2 och så vidare till terminalen eller bladnoden.
• Grad - Det är antalet underträd i en nod i ett givet träd.
• Djup - Det är den maximala nivån för någon nod i ett givet träd och även känd som höjd.
• Terminalnod - Noden med den högsta nivån är terminalnod medan andra noder utom terminal- och rotnoden kallas icke-terminala noder.

Definition av graf

EN Graf är också en matematisk icke-linjär datastruktur som kan representera olika typer av fysisk struktur. Den består av en grupp vertikaler (eller noder) och uppsättning kanter som förbinder de två topparna. Vertikaler på diagrammet representeras som punkt eller cirklar och kanter visas som bågar eller linjesegment. En kant representeras av E (v, w) där v och w är paret av topparna. Avlägsnande av en kant från en krets eller ansluten graf skapar en subgraf som är ett träd.

Graferna klassificeras i olika kategorier såsom riktad, icke-riktad, ansluten, icke-ansluten, enkel och multigraf. Datornätverk, transportsystem, diagram över sociala nätverk, elektriska kretsar och projektplanering är några av tillämpningarna för grafdatastruktur. Det används också i ledningsteknik benämnd som NÄSVIS (programutvärdering och granskningsteknik) och CPM (kritisk sökmetod) där grafstrukturen analyseras.

Egenskaper för en graf:

• En topp i ett diagram kan anslutas till valfritt antal andra vertikaler med kanter.
• En kant kan vridas eller riktas.
• En kant kan vägas.

I diagrammet använder vi också olika termer som angränsande vertikaler, sökväg, cykel, grad, ansluten graf, komplett graf, viktad graf osv. Låt oss förstå några av dessa termer.

• Intilliggande vertikaler - Ett toppunkt a ligger intill toppet b om det finns en kant (a, b) eller (b, a).
• Väg - En väg från ett slumpmässigt toppunkt w är en intilliggande sekvens av vertikaler.
• Cykel - Det är en väg där den första och den sista vertikalen är densamma.
• Grad - Det är ett antal kanter på ett toppunkt.
• Ansluten graf - Om det finns en sökväg från ett slumpmässigt toppunkt till något annat toppunkt, är den grafen känd som en ansluten graf.

1. I ett träd finns det bara en bana mellan två tvärhörn medan en graf kan ha enkelriktad och dubbelriktad väg mellan noderna.
2. I trädet finns exakt en rotnod, och varje barn kan bara ha en förälder. Till skillnad från i ett diagram finns det inget begrepp om rotnoden.
3. Ett träd kan inte ha slingor och självslingor medan diagram kan ha slingor och självslingor.
4. Grafer är mer komplicerade eftersom det kan ha slingor och självslingor. Däremot är träd enkla jämfört med diagrammet.
5. Trädet korsas med hjälp av förbeställning, ordning och efterbeställningstekniker. Å andra sidan använder vi BFS (Breadth First Search) och DFS (Depth First Search) för grafkorsning.
6. Ett träd kan ha n-1 kanter. Tvärtom, i diagrammet finns inget fördefinierat antal kanter, och det beror på diagrammet.
7. Ett träd har en hierarkisk struktur medan graf har en nätverksmodell.

Slutsats

Graf och träd är den icke-linjära datastrukturen som används för att lösa olika komplexa problem. En graf är en grupp av toppar och kanter där en kant ansluter ett par toppar medan ett träd betraktas som ett minimalt anslutet diagram som måste vara anslutet och fritt från slingor.