Graf datastruktur og Algorithms (Eksempel)

Hvad er en graf i datastruktur?

En graf er en ikke-lineær datastruktur, der består af toppunkter og kanter, hvor toppunkter indeholder informationen eller dataene, og kanterne fungerer som et bindeled mellem par af toppunkter.

Det bruges til at løse rigtige ordproblemer som at finde den bedste rute til destinationsstedet og ruten til telekommunikation og sociale netværk. Brugere betragtes som en node i grafen, og ledningerne er de kanter, der forbinder brugerne.

Hvis kanter er repræsenteret som E og hjørner er repræsenteret som V, så kan grafen G skrives som mængden af ​​hjørner og kanter, som f.eks. G (V, E)

Eksempel på graf i datastruktur

Her er et simpelt eksempel på grafdatastruktur:

Eksempel på graf i datastruktur

Det er en simpel urettet graf (en slags graf). Her er sættet af toppunkt: {A, B, C,D,E,F}. To hjørner skaber en kant. For eksempel er A og B forbundet med en kant. A og F er dog ikke forbundet med nogen kanter.

Grafterminologier i datastruktur

Følgende er nogle vigtige udtryk, der bruges i grafdatastruktur:

Semester Produktbeskrivelse
Vertex Alle dataelementer kaldes et vertex eller en node. I ovenstående billede er A, B, C, D & E hjørnerne.
Kant (bue) Forbindende forbindelser mellem to noder eller toppunkter kaldes kant (Arc). Den har to ender og er repræsenteret som (startendeVertex, endingVertex).
Udirigeret kant Det er en tovejs kant.
Instrueret Edge Det er en ensrettet kant.
Vægtet kant En kant med værdi på.
Degree I Graph kaldes antallet af kanter forbundet med et toppunkt en grad.
Indegree Det samlede antal indkommende kanter forbundet til et toppunkt.
Udgrade Det samlede antal udgående kanter forbundet til et toppunkt.
Selvløkke En kant kaldes en selvløkke, hvis dens to endepunkter falder sammen.
Tilknytning Hjørner siges at være tilstødende, hvis en kant er forbundet.

Typer af grafer i datastruktur

Her er listen over de mest almindelige typer af grafer i datastrukturen:

  • Instrueret graf
  • Udirigeret graf
  • Vægtet graf
  • Tovejs graf
  • Uendelig graf
  • Nul graf
  • Triviel graf
  • Multi graf
  • Komplet graf
  • Forbundet graf
  • Cyklisk graf
  • Instrueret acyklisk graf (DAG)
  • Cyklus graf
  • Bipartitegraf
  • Euler graf
  • Hamilton graf

Anvendelser af grafdatastruktur

En graf har mange use cases. Der er mange algoritmer, der bruger Graphs meget. Her er nogle af grafens applikationer:

  • Google Maps bruger grafer til at finde skæringspunktet mellem to veje og beregne afstanden mellem to steder.
    For eksempel: Dijkstra, for at finde den korteste afstand mellem kilde og destination.
  • Facebook bruger Graphs til at finde brugernes fælles ven. Dens algoritme betragter hver bruger som en knude på en graf.
  • Til ressourceallokering anvendes DAG (Direct Acyclic Graph). Det kontrollerer ressourcernes afhængighed.
  • Google Search Engine bruger grafer til at skabe placeringen for websteder.
  • En kortlægningsenhed bruger grafdatastrukturen.
  • router og t's protokol bruger grafen til at lære stien til destinationsstien.