Innhold

• Sammenligningstabell
• Definisjon av tre
• Egenskaper til tre:
• Definisjon av graf
• Egenskaper til en graf:
• Konklusjon

Tre og graf kommer under kategorien ikke-lineær datastruktur der tre tilbyr en veldig nyttig måte å representere et forhold mellom nodene i en hierarkisk struktur og graf følger en nettverksmodell. Tre og graf er differensiert av det faktum at en trestruktur må være koblet sammen og aldri kan ha løkker mens det i grafen ikke er noen slike begrensninger.

En ikke-lineær datastruktur består av en samling av elementene som er fordelt på et plan, noe som betyr at det ikke er en slik sekvens mellom elementene som de eksisterer i en lineær datastruktur.

1. 1. Sammenligningstabell
   2. Definisjon
   3. Viktige forskjeller
   4. Konklusjon

Sammenligningstabell

Grunnlag for sammenligning	Tre	Kurve
Sti	Bare en mellom to hjørner.	Mer enn en bane er tillatt.
Rotknute	Den har nøyaktig en rotnode.	Grafen har ikke en rotknute.
Loops	Ingen sløyfer er tillatt.	Graf kan ha løkker.
kompleksitet	Mindre sammensatt	Mer sammensatt relativt
Gjennomgangsteknikker	Forhåndsbestilling, Forhåndsbestilling og Etterbestilling.	Bredde-første søk og dybde-første søk.
Antall kanter	n-1 (der n er antall noder)	Ikke definert
Modelltype	Hierarkisk	Network

Definisjon av tre

EN tre er en begrenset samling av dataelementer vanligvis betegnet som noder. Som det er nevnt over at et tre er en ikke-lineær datastruktur som ordner dataelementer i sortert rekkefølge. Det brukes til å vise en hierarkisk struktur mellom de forskjellige dataelementene og organisere dataene i grener som relaterer informasjonen. Tilsetningen av en ny kant i et tre resulterer i en dannelse av løkken eller kretsen.

Det er flere typer trær, for eksempel et binærtre, binært søketre, AVL-tre, gjenget binærtre, B-tre, etc. Datakomprimering, fillagring, manipulering av det aritmetiske uttrykket og vilttrær er noe av anvendelsen av tre data struktur.

Egenskaper til tre:

• Det er utpekt node på toppen av treet kjent som en rot av treet.
• De gjenværende dataelementene er delt inn i usammenhengende undergrupper refererer til som undertrinn.
• Treet utvides i høyden mot bunnen.
• Det må kobles et tre som betyr at det må være en bane fra en rot til alle andre noder.
• Den inneholder ingen løkker.
• Et tre har n-1 kanter.

Det er forskjellige betegnelser assosiert med trær som terminalnode, kant, nivå, grad, dybde, skog osv. Blant disse begrepene er noen av dem beskrevet nedenfor.

• Kant - En linje som forbinder to noder.
• Nivå - Et tre er delt inn i nivåer slik at rotnoden er på nivå 0. Deretter er dets nærmeste barn på nivå 1, og dets nærmeste barn er på nivå 2 og så videre opp til terminalen eller bladnoden.
• Grad - Det er antall undertrær av en node i et gitt tre.
• Dybde - Det er maksimalnivået på en hvilken som helst nod i et gitt tre, og også kjent som høyde.
• Terminalnode - Noden på høyeste nivå er terminalnode, mens andre noder unntatt terminal- og rotnode er kjent som ikke-terminale noder.

Definisjon av graf

EN kurve er også en matematisk ikke-lineær datastruktur som kan representere forskjellige typer fysisk struktur. Den består av en gruppe av hjørnene (eller knutepunktene) og sett med kanter som forbinder de to toppunktene. Vertikater på grafen er representert som punkt eller sirkler og kanter vises som buer eller linjesegmenter. En kant er representert med E (v, w) der v og w er parene av toppunktene. Fjerning av en kant fra en krets eller tilkoblet graf oppretter en undergraf som er et tre.

Grafene er klassifisert i forskjellige kategorier som regisserte, ikke-rettede, tilkoblede, ikke-tilkoblede, enkle og flergrafiske. Datanettverk, transportsystem, sosialt nettverksdiagram, elektriske kretsløp og prosjektplanlegging er noen av anvendelsene av grafdatastruktur. Det er også ansatt i ledelsesteknikk kalt som PERT (programevaluering og gjennomgangsteknikk) og CPM (kritisk banemetode) der grafstrukturen analyseres.

Egenskaper til en graf:

• Et toppunkt i en graf kan kobles til et hvilket som helst antall andre hjørner ved hjelp av kanter.
• En kant kan rettes i retning.
• En kant kan vektes.

I graf bruker vi også forskjellige uttrykk som tilstøtende vertekser, bane, syklus, grad, tilkoblet graf, komplett graf, vektet graf osv. La oss forstå noen av disse begrepene.

• Tilstøtende hjørner - Et toppunkt a er tilstøtende til toppunktet b hvis det er en kant (a, b) eller (b, a).
• Sti - En bane fra et tilfeldig toppunkt w er en tilstøtende sekvens av toppunkt.
• Syklus - Det er en bane der den første og den siste hjørnet er den samme.
• Grad - Det er en rekke kanter hendende i en toppunkt.
• Tilkoblet graf - Hvis det finnes en bane fra et tilfeldig toppunkt til noe annet toppunkt, er grafen kjent som en tilkoblet graf.

1. I et tre finnes det bare en bane mellom to toppunkt, mens en graf kan ha enveis- og toveisveier mellom nodene.
2. I treet er det nøyaktig en rotnode, og hvert barn kan bare ha én forelder. I motsetning til i en graf, er det ingen begrep om rotnoden.
3. Et tre kan ikke ha løkker og selvløkker, mens grafen kan ha løkker og selvløkker.
4. Grafer er mer kompliserte ettersom det kan ha løkker og selvløkker. I kontrast er trær enkle sammenlignet med grafen.
5. Treet krysses ved hjelp av forhåndsbestilling, ordre og etter ordre. På den andre siden bruker vi BFS (Breadth First Search) og DFS (Deepth First Search) for grafoverføring.
6. Et tre kan ha n-1 kanter. Tvert imot, i grafen er det ikke et forhåndsdefinert antall kanter, og det avhenger av grafen.
7. Et tre har en hierarkisk struktur mens graf har en nettverksmodell.

Konklusjon

Graf og tre er den ikke-lineære datastrukturen som brukes til å løse forskjellige komplekse problemer. En graf er en gruppe av hjørner og kanter der en kant forbinder et par toppunkt, mens et tre anses som en minimalt tilkoblet graf som må være tilkoblet og fri for løkker.