I denne vejledning lærer du, hvad en grafdatastruktur er. Du finder også repræsentationer af en graf.
En grafdatastruktur er en samling af noder, der har data og er forbundet til andre noder.
Lad os prøve at forstå dette gennem et eksempel. På facebook er alt en knude. Det inkluderer bruger, foto, album, begivenhed, gruppe, side, kommentar, historie, video, link, note … alt, der har data, er en node.
Hvert forhold er en kant fra en node til en anden. Uanset om du sender et foto, deltager i en gruppe, som en side osv., Oprettes der en ny kant til det forhold.
Eksempel på grafdatastruktur
Hele facebook er så en samling af disse noder og kanter. Dette skyldes, at facebook bruger en grafdatastruktur til at gemme sine data.
Mere præcist er en graf en datastruktur (V, E), der består af
- En samling af hjørner V
- En samling kanter E, repræsenteret som ordnede par af 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
- Adjacency : Et toppunkt siges at støde op til et andet toppunkt, hvis der er en kant, der forbinder dem. Hjørner 2 og 3 er ikke tilstødende, fordi der ikke er nogen kant imellem dem.
- Sti : En sekvens af kanter, der giver dig mulighed for at gå fra toppunkt A til toppunkt B kaldes en sti. 0-1, 1-2 og 0-2 er stier fra toppunkt 0 til toppunkt 2.
- Directed Graph : En graf, hvor en kant (u, v) ikke nødvendigvis betyder, at der også er en kant (v, u). Kanterne i en sådan graf er repræsenteret af pile for at vise kantens retning.
Grafrepræsentation
Grafer er almindeligt repræsenteret på to måder:
1. Adjacency Matrix
En nærhedsmatrix er et 2D-array med V x V-hjørner. Hver række og kolonne repræsenterer et toppunkt.
Hvis værdien af et hvilket som helst element a(i)(j)er 1, repræsenterer det, at der er en kant, der forbinder toppunkt i og toppunkt j.
Nærhedsmatrixen for den graf, vi oprettede ovenfor, er
Matrix til graflig tilknytning
Da det er en ikke-rettet graf, for kant (0,2), skal vi også markere kant (2,0); hvilket gør adjacency matrix symmetrisk omkring diagonalen.
Kantopslag (kontrol af, om der findes en kant mellem toppunkt A og toppunkt B) er ekstremt hurtig i nærhedsmatrixrepræsentation, men vi er nødt til at reservere plads til alle mulige forbindelser mellem alle hjørner (V x V), så det kræver mere plads.
2. Tilstødelsesliste
En nærhedsliste repræsenterer en graf som en matrix af sammenkædede lister.
Indekset for arrayet repræsenterer et toppunkt, og hvert element i dets sammenkædede liste repræsenterer de andre hjørner, der danner en kant med toppunktet.
Nærhedslisten for den graf, vi lavede i det første eksempel, er som følger:
Repræsentation af tilstødende liste
En nærhedsliste er effektiv med hensyn til opbevaring, fordi vi kun behøver at gemme værdierne for kanterne. For en graf med millioner af hjørner kan dette betyde meget sparet plads.
Grafoperationer
De mest almindelige grafhandlinger er:
- Kontroller, om elementet er til stede i grafen
- Grafgennemgang
- Tilføj elementer (toppunkt, kanter) til grafen
- At finde stien fra et toppunkt til et andet
