Graf datastruktur og Algorithms (Eksempel)
Sarah Chen
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:
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 | Beskrivelse |
|---|---|
| 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.
