Graf datastruktur og Algorithms (Eksempel)
Sarah Chen
⚡ Smart oppsummering
Grafdatastruktur er en ikke-lineær samling av hjørner og kanter der hver kant kobler sammen et par hjørner. Grafer modellerer virkelige nettverk som kart, sosiale forbindelser og nettsider, og støtter mange kraftige algoritmer.
Hva er en graf i datastruktur?
En graf er en ikke-lineær datastruktur som består av hjørner og kanter, der hjørnene inneholder informasjonen eller dataene, og kantene fungerer som en kobling mellom et par hjørner.
Den brukes til å løse problemer i den virkelige verden, som å finne den beste ruten til destinasjonen og ruten for telekommunikasjon og sosiale nettverk. Brukere regnes som en node i grafen, og ledningene er kantene som forbinder brukerne.
Hvis kanter er representert som E og toppunkter er representert som V, så kan grafen G skrives som sett med toppunkter og kanter, som f.eks. G (V, E).
Eksempel på graf i datastruktur
Her er et enkelt eksempel på en grafdatastruktur:
Det er en enkel, urettet graf (én type graf). Her er mengden av noder: {A, B, C, D, E, F}. To noder danner en kant. For eksempel er A og B koblet sammen med en kant. A og F er imidlertid ikke koblet sammen med noen kanter.
Grafiske terminologier i datastruktur
Følgende er noen viktige begreper som brukes i grafdatastrukturen:
| Begrep | Tekniske beskrivelser |
|---|---|
| Vertex | Hvert dataelement kalles et hjørne eller en node. I bildet ovenfor er A, B, C, D og E hjørnene. |
| Kant (bue) | Forbindelsesledd mellom to noder eller hjørner kalles en kant (bue). Den har to ender og er representert som (startKnopp, endingKnopp). |
| Udirigert kant | Det er en toveis kant. |
| Regissert Edge | Det er en ensrettet kant. |
| Vektet kant | En fordel med en verdi på seg. |
| Grad | I en graf kalles antallet kanter forbundet med et hjørne en grad. |
| Indegree | Det totale antallet innkommende kanter koblet til et toppunkt. |
| Utgradert | Det totale antallet utgående kanter koblet til et toppunkt. |
| Selvløkke | En kant kalles en selvløkke hvis de to endepunktene sammenfaller. |
| Tilstøtelse | Noder sies å være tilstøtende hvis en kant er forbundet mellom dem. |
Typer grafer i datastruktur
Her er listen over de vanligste typer grafer i datastrukturen:
- Regissert graf
- Udirigert graf
- Vektet graf
- Toveis graf
- Uendelig graf
- Null graf
- Triviell graf
- Multi Graph
- Komplett graf
- Tilkoblet graf
- Syklisk graf
- Regissert syklisk graf (DAG)
- Syklusgraf
- Todelt graf
- Euler graf
- Hamilton-graf
Hvordan representere en graf i datastruktur?
En graf lagres vanligvis i minnet ved hjelp av én av to representasjoner. Valget påvirker hvor mye minne grafen bruker og hvor raskt vanlige operasjoner kjører.
- Nærhetsmatrise: En todimensjonal V × V-matrise der celle [i][j] er 1 (eller kantvekten) hvis det finnes en kant mellom hjørne i og hjørne j, og 0 ellers. Den tillater O(1) kantoppslag, men bruker O(V²)-rom, noe som gjør den best for tette grafer.
- Nærhetsliste: En matrise med lister der hvert hjørne lagrer en liste over sine nærliggende hjørner. Den bruker O(V + E)-rom og er effektiv for sparsomme grafer, og det er derfor de fleste grafer i den virkelige verden bruker den.
Du kan lese mer om disse i tilstøtende liste og matriserepresentasjon av en graf opplæringen.
Anvendelser av grafdatastruktur
En graf har mange bruksområder. Det finnes mange algoritmer som bruker grafer. Her er noen av bruksområdene til grafen:
- Google Kart bruker grafer for å finne krysset mellom to veier og beregne avstanden mellom to steder. For eksempel, Dijkstra, for å finne den korteste avstanden mellom kilde- og destinasjonsstedet.
- Facebook bruker grafer for å finne brukernes felles venner. Algoritmen deres betrakter hver bruker som en node i en graf.
- For ressursallokering brukes en DAG (Directed Acyclic Graph). Den kontrollerer ressursenes avhengighet.
- Ocuco Google Søkemotorer bruker grafer for å lage rangeringen for nettsteder.
- Et kartping Enheten bruker grafdatastrukturen.
- A router og protokollen bruker grafen til å lære banen til destinasjonen.
