Graf datastruktur og Algorithms (Eksempel)
Sarah Chen
Hva er en graf i datastruktur?
En graf er en ikke-lineær datastruktur som består av toppunkter og kanter, der toppunkter inneholder informasjonen eller dataene, og kantene fungerer som en kobling mellom par av toppunkter.
Den brukes til å løse ekte ordproblemer som å finne den beste ruten til destinasjonsstedet og ruten for telekommunikasjon og sosiale nettverk. Brukere betraktes 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å grafdatastruktur:
Det er en enkel urettet graf (en slags graf). Her er settet med toppunkt: {A, B, C,D,E,F}. To hjørner skaper en kant. For eksempel er A og B knyttet til en kant. A og F er imidlertid ikke knyttet til noen kanter.
Grafiske terminologier i datastruktur
Følgende er noen viktige termer som brukes i grafdatastruktur:
| Begrep | Tekniske beskrivelser |
|---|---|
| Vertex | Alle dataelementer kalles et toppunkt eller en node. I bildet ovenfor er A, B, C, D og E toppunktene. |
| Kant (bue) | Koblingskoblinger mellom to noder eller toppunkter kalles edge (Arc). Den har to ender og er representert som (startendeVertex, endingVertex). |
| Udirigert kant | Det er en toveis kant. |
| Regissert Edge | Det er en ensrettet kant. |
| Vektet kant | En kant med verdi på seg. |
| Grad | I Graph kalles antall kanter koblet til et toppunkt 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 | Topppunkter sies å være tilstøtende hvis en kant er koblet sammen. |
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
Anvendelser av grafdatastruktur
En graf har mange brukstilfeller. Det er mange algoritmer som bruker Graphs mye. Her er noen av applikasjonene til grafen:
- Google Maps bruker grafer for å finne skjæringspunktet mellom to veier og beregne avstanden mellom to steder.
For eksempel, Dijkstra, for å finne den korteste avstanden mellom kilde og destinasjonssted. - Facebook bruker Graphs for å finne den felles vennen til brukerne. Algoritmen betrakter hver bruker som en node i en graf.
- For ressursallokering brukes DAG (Direct Acyclic Graph). Den sjekker ressursens avhengighet.
- Googles søkemotor bruker grafer for å lage rangeringen for nettsteder.
- En kartleggingsenhet bruker grafdatastrukturen.
- router og ts protokoll bruker Graph for å lære banen til destinasjonsbanen.
