I denne opplæringen lærer du hva en grafdatastruktur er. Du vil også finne fremstillinger av en graf.
En grafdatastruktur er en samling noder som har data og er koblet til andre noder.
La oss prøve å forstå dette gjennom et eksempel. På facebook er alt en node. Det inkluderer bruker, foto, album, begivenhet, gruppe, side, kommentar, historie, video, lenke, merknad … alt som har data er en node.
Hvert forhold er en kant fra en node til en annen. Enten du legger ut et bilde, blir med i en gruppe, som en side osv., Opprettes en ny kant for det forholdet.
Eksempel på grafdatastruktur
Hele facebook er da en samling av disse noder og kanter. Dette er fordi facebook bruker en grafdatastruktur for å lagre dataene.
Mer presist er en graf en datastruktur (V, E) som består av
- En samling av hjørner V
- En samling kanter E, representert som ordnede par av hjørner (u, v)
Hjørner og kanter
I grafen,
V = (0, 1, 2, 3) E = ((0,1), (0,2), (0,3), (1,2)) G = (V, E)
Grafterminologi
- Tilstøtende : Et toppunkt sies å ligge ved siden av et annet toppunkt hvis det er en kant som forbinder dem. Vertices 2 og 3 er ikke tilstøtende fordi det ikke er noen kant mellom dem.
- Sti : En sekvens av kanter som lar deg gå fra toppunkt A til toppunkt B kalles en sti. 0-1, 1-2 og 0-2 er baner fra toppunkt 0 til toppunkt 2.
- Regissert graf : En graf der en kant (u, v) ikke nødvendigvis betyr at det også er en kant (v, u). Kantene i en slik graf er representert med piler for å vise kantretningen.
Grafrepresentasjon
Grafer er ofte representert på to måter:
1. Adjacency Matrix
En tilknytningsmatrise er et 2D-utvalg av V x V-hjørner. Hver rad og kolonne representerer et toppunkt.
Hvis verdien av et hvilket som helst element a(i)(j)er 1, representerer det at det er en kant som forbinder toppunkt i og toppunkt j.
Nærmaktsmatrisen for grafen vi opprettet ovenfor er
Matriser for graflig tilknytning
Siden det er en ikke-rettet graf, for kant (0,2), må vi også merke kant (2,0); gjør tilgrensematrisen symmetrisk om diagonalen.
Kantoppslag (å sjekke om det eksisterer en kant mellom toppunkt A og toppunkt B) er ekstremt raskt i matriserepresentasjon, men vi må reservere plass til alle mulige koblinger mellom alle toppunktene (V x V), så det krever mer plass.
2. Tilstøtningsliste
En tilknytningsliste representerer en graf som en rekke lenker.
Indeksen til matrisen representerer et toppunkt, og hvert element i den tilknyttede listen representerer de andre toppunktene som danner en kant med toppunktet.
Tilstøtningslisten for grafen vi laget i det første eksemplet er som følger:
Tilstøtningslistrepresentasjon
En nærhetsliste er effektiv når det gjelder lagring fordi vi bare trenger å lagre verdiene for kantene. For en graf med millioner av hjørner kan dette bety mye lagret plass.
Grafoperasjoner
De vanligste grafoperasjonene er:
- Sjekk om elementet er til stede i grafen
- Grafgjennomgang
- Legg til elementer (toppunkt, kanter) i grafen
- Finne stien fra et toppunkt til et annet
