Anbefalt, 2021

Redaksjonens

Forskjell mellom tre og graf

Trær og graf kommer under kategorien ikke-lineær datastruktur der tre gir en veldig nyttig måte å representere et forhold mellom noder i en hierarkisk struktur og graf følger en nettverksmodell. Trær og graf er differensiert av det faktum at en trestruktur må være koblet og aldri kan ha sløyfer, mens i grafen er det ingen slike restriksjoner.

En ikke-lineær datastruktur består av en samling av elementene som er fordelt på et fly som betyr at det ikke finnes en slik sekvens mellom elementene som den eksisterer i en lineær datastruktur.

Sammenligningstabel

Grunnlag for sammenligningTreKurve
StiBare en mellom to hjørner.Mer enn en sti er tillatt.
RotnøkkelDen har nøyaktig en rotnode.Graf har ikke en rotnode.
LoopsIngen løkker er tillatt.Graf kan ha løkker.
kompleksitetMindre kompleksMer komplisert relativt
Traversal teknikkerPre-order, In-order og Post-order.Bredde-første søk og dybde-første søk.
Antall kantern-1 (hvor n er antall noder)Ikke definert
Modell typeHierarkiskNetwork

Definisjon av tre

Et tre er en endelig samling av dataposter som vanligvis betegnes som noder. Som nevnt ovenfor er et tre en ikke-lineær datastruktur som ordner dataposter i rekkefølge. Det brukes til å vise en hierarkisk struktur mellom de ulike dataelementene og organiserer dataene i grener som relaterer informasjonen. Tillegg av en ny kant i et tre resulterer i en formasjon av sløyfen eller kretsen.

Det finnes flere typer trær som et binært tre, binært søketre, AVL-tre, gjenget binært tre, B-tre osv. Datakomprimering, arkivering, manipulering av det aritmetiske uttrykket og spilltrærne er noe av bruken av treet data struktur.

Egenskaper av treet:

  • Det er utpekt knutepunkt øverst på treet kjent som en rot av treet.
  • De gjenværende datapostene er delt inn i disjoint undergrupper, referert til som subtree.
  • Træret er utvidet i høyden mot bunnen.
  • Et tre må være koblet, noe som betyr at det må være en sti fra en rot til alle andre noder.
  • Den inneholder ingen løkker.
  • Et tre har n-1 kanter.

Det er ulike termer knyttet til trær som terminal node, kant, nivå, grad, dybde, skog, etc. Blant disse vilkårene, er noen av dem beskrevet nedenfor.

  • Kant - En linje som forbinder to noder.
  • Nivå - Et tre er delt inn i nivåer på en slik måte at rotnoden er på nivå 0. Deretter er de nærmeste barna på nivå 1, og de nærmeste barna er på nivå 2 og så videre opp til terminalen eller bladknuten.
  • Grad - Det er antall subtreer av en node i et gitt tre.
  • Dybde - Det er maksimumsnivået til en node i et gitt tre og også kjent som høyde .
  • Terminal node - Høyeste nivå node er terminal node mens andre noder unntatt terminal og root node er kjent som ikke-terminale noder.

Definisjon av graf

En graf er også en matematisk ikke-lineær datastruktur som kan representere ulike typer fysisk struktur. Den består av en gruppe vertikaler (eller noder) og sett med kanter som forbinder de to vertikaler. Vertikaler på grafen er representert som punkt eller sirkler og kanter vises som buer eller linjesegmenter. En kant er representert ved E (v, w) hvor v og w er parene av vertikaler. Fjerning av en kant fra en krets eller tilkoblet graf skaper en subgraph som er et tre.

Grafer er klassifisert i ulike kategorier, for eksempel instruert, ikke-rettet, tilkoblet, ikke-tilkoblet, enkel og multi-graf. Datanettverk, transportsystem, sosiale nettverkskort, elektriske kretser og prosjektplanlegging er noen av bruksområdene til grafdatastruktur. Det er også ansatt i ledelsesteknikk kalt PERT (program evaluering og gjennomgangsteknikk) og CPM (kritisk banemetode) der grafstrukturen analyseres.

Egenskaper av en graf:

  • Et toppunkt i en graf kan kobles til et hvilket som helst antall andre vinkler ved hjelp av kanter.
  • En kant kan bli direkte eller rettet.
  • En kant kan vektes.

I graf bruker vi også ulike termer som tilstøtende kryss, vei, syklus, grad, koblet graf, komplett graf, vektet graf etc. La oss forstå noen av disse vilkårene.

  • Tilgrensende hjørner - Et toppunkt a ligger ved siden av vertex b hvis det er en kant (a, b) eller (b, a).
  • Sti - En sti fra et tilfeldig vertex w er en tilstøtende sekvens av punkter.
  • Syklus - Det er en sti hvor de første og siste kryssene er de samme.
  • Grad - Det er en rekke kanter hendelse på et toppunkt.
  • Koblet graf - Hvis det finnes en bane fra et tilfeldig vertex til et annet toppunkt, så er grafen kjent som en koblet graf.

Viktige forskjeller mellom tre og graf

  1. I et tre eksisterer det bare en bane mellom noen to hjørner, mens en graf kan ha enveis og toveisbaner mellom knutepunktene.
  2. I treet er det akkurat en rotnode, og hvert barn kan bare ha en forelder. I motsetning til, i en graf, er det ikke noe konsept for rotnoden.
  3. Et tre kan ikke ha løkker og selvløkker mens grafen kan ha sløyfer og selvløkker.
  4. Grafer er mer kompliserte, da det kan ha sløyfer og selvløkker. Derimot er trærne enkle sammenlignet med grafen.
  5. Træret er krysset ved hjelp av forhåndsordre-, ordre- og postorderteknikker. På den annen side bruker vi BFS (bredde første søk) og DFS (dybde første søk) for graf-traversal.
  6. Et tre kan ha n-1 kanter. Tvert imot, i grafen, er det ikke forhåndsdefinert antall kanter, og det avhenger av grafen.
  7. Et tre har en hierarkisk struktur mens grafen har en nettverksmodell.

Konklusjon

Graf og tre er den ikke-lineære datastrukturen som brukes til å løse ulike komplekse problemer. En graf er en gruppe av vinkler og kanter hvor en kant forbinder et par krysser, mens et tre betraktes som en minimal koblet graf som må være koblet og fri fra sløyfer.

Top