Anbefalet, 2022

Redaktørens Valg

Forskel mellem træ og graf

Træ og graf henhører under kategorien ikke-lineær datastruktur, hvor træ giver en meget nyttig måde at repræsentere et forhold mellem noderne i en hierarkisk struktur på, og graf følger en netværksmodel. Træ og graf er differentieret af, at en træstruktur skal forbindes og aldrig kunne have sløjfer, mens der i grafen ikke findes sådanne begrænsninger.

En ikke-lineær datastruktur består af en samling af de elementer, der er fordelt på et plan, hvilket betyder, at der ikke er nogen sådan sekvens mellem elementerne som den eksisterer i en lineær datastruktur.

Sammenligningstabel

Grundlag for sammenligningTræKurve
StiKun en mellem to hjørner.Mere end en sti er tilladt.
RodknudeDen har nøjagtigt en rodknude.Grafen har ikke en rodknude.
loopsIngen sløjfer er tilladt.Grafen kan have sløjfer.
kompleksitetMindre kompleksMere kompleks forholdsvis
Traversal teknikkerForbestilling, I-bestilling og Post-order.Bredde-første søgning og dybde-første søgning.
Antal kantern-1 (hvor n er antallet af noder)Ikke defineret
Model typeHierarkiskNetværk

Definition af træ

Et træ er en endelige samling af dataposter, der normalt betegnes som knuder. Som det er nævnt ovenfor, er et træ en ikke-lineær datastruktur, som arrangerer dataposter i rækkefølge. Det bruges til at vise en hierarkisk struktur mellem de forskellige dataelementer og organiserer dataene i grene, der relaterer oplysningerne. Tilføjelsen af ​​en ny kant i et træ resulterer i en dannelse af sløjfen eller kredsløbet.

Der er flere typer træer, såsom et binært træ, binært søgetræ, AVL-træ, trådt binærtræ, B-træ osv. Datakomprimering, arkivering, manipulation af det aritmetiske udtryk og spiltræer er noget af anvendelsen af ​​træ datastruktur.

Træets egenskaber:

  • Der er udpeget knude øverst på træet kendt som en rod af træet.
  • De resterende dataelementer er opdelt i disjoint undergrupper henvises til som subtree.
  • Træet er udvidet i højden mod bunden.
  • Et træ skal forbindes, hvilket betyder, at der skal være en sti fra en rod til alle andre knuder.
  • Det indeholder ingen løkker.
  • Et træ har n-1 kanter.

Der er forskellige termer i forbindelse med træer som terminal node, kant, niveau, grad, dybde, skov osv. Blandt disse termer er nogle af dem beskrevet nedenfor.

  • Kant - En linje, som forbinder to noder.
  • Niveau - Et træ er opdelt i niveauer på en sådan måde, at rodknuden er på niveau 0. Derefter er dens umiddelbare børn på niveau 1, og dens umiddelbare børn er på niveau 2 og så videre op til terminalen eller bladknuden.
  • Grad - Det er antallet af subtre af en node i et givet træ.
  • Dybde - Det er det maksimale niveau for en node i et givet træ og også kendt som højde .
  • Terminal node - Det højeste niveau knudepunkt er terminal node, mens andre noder undtagen terminal og root node er kendt som ikke-terminale noder.

Definition af graf

En graf er også en matematisk ikke-lineær datastruktur, som kan repræsentere forskellige former for fysisk struktur. Den består af en gruppe af hjørner (eller knuder) og sæt af kanter, som forbinder de to hjørner. Grafer på grafen er repræsenteret som punkt eller cirkler, og kanter vises som buer eller linjesegmenter. En kant er repræsenteret ved E (v, w), hvor v og w er parrene af hjørner. Fjernelse af en kant fra et kredsløb eller tilsluttet graf skaber en subgraph, der er et træ.

Graferne er klassificeret i forskellige kategorier som direkte, ikke-rettet, tilsluttet, ikke-tilsluttet, enkel og multi-graf. Computer netværk, transport system, sociale netværk graf, elektriske kredsløb og projektplanlægning er nogle af de applikationer af graf data struktur. Det er også ansat i ledelsesteknik, der er opkaldt som PERT (programevaluering og gennemgangsteknik) og CPM (kritisk vejmetode), hvor grafstrukturen analyseres.

Egenskaber for en graf:

  • Et hjørne i en graf kan forbindes til et hvilket som helst antal andre hjørner ved hjælp af kanter.
  • En kant kan være vejledende eller rettet.
  • En kant kan vægtes.

I graf bruger vi også forskellige udtryk som tilstødende hjørner, sti, cyklus, grad, tilsluttet graf, komplet graf, vægtet graf osv. Lad os forstå nogle af disse udtryk.

  • Tilgrænsende hjørner - En vinkel a ligger ved siden af ​​vertex b, hvis der er en kant (a, b) eller (b, a).
  • Sti - En sti fra et tilfældigt vertex w er en tilstødende sekvens af hjørner.
  • Cyklus - Det er en sti, hvor de første og sidste hjørner er de samme.
  • Grad - Det er en række kanter, der forekommer på et vertex.
  • Tilknyttet graf - Hvis der findes en sti fra et tilfældigt vertex til et hvilket som helst andet toppunkt, så er den graf kendt som en tilsluttet graf.

Nøgleforskelle mellem træ og graf

  1. I et træ eksisterer der kun en vej mellem de to to hjørner, medens en graf kan have ensretnings- og tovejsstier mellem knudepunkterne.
  2. I træet er der nøjagtigt en rodknude, og hvert barn kan kun have en forælder. I modsætning til, i en graf er der intet koncept af rodknuden.
  3. Et træ kan ikke have sløjfer og selvløkker, mens graf kan have sløjfer og selvløkker.
  4. Grafer er mere komplicerede, da det kan have sløjfer og selvløkker. I modsætning hertil er træer enkle sammenlignet med grafen.
  5. Træet krydses ved hjælp af forudbestillings-, i-ordnings- og postorderteknikker. På den anden side bruger vi BFS (Breadth First Search) og DFS (Dyb First Search) til graf-traversal.
  6. Et træ kan have n-1 kanter. Tværtimod er der i grafen ikke noget foruddefineret antal kanter, og det afhænger af grafen.
  7. Et træ har en hierarkisk struktur, mens grafen har en netværksmodel.

Konklusion

Graf og træ er den ikke-lineære datastruktur, som bruges til at løse forskellige komplekse problemer. En graf er en gruppe af hjørner og kanter, hvor en kant forbinder et par hjørner, medens et træ betragtes som en minimalt forbundet graf, der skal forbindes og fri for sløjfer.

Top