Adjacency List og Matrix Repræsentation af Graph
Sarah Chen
Selvom de ser anderledes ud, alle sammen typer af grafer kan repræsenteres på lignende måde. Der er generelt to typer grafrepræsentation:
- Adjacency Matrix
- Tilstødelsesliste
Tilstødelsesliste
Adjacency List består af Linked Lists. Hvert vertex betragtes som et matrixindeks, og hvert element repræsenterer en sammenkædet liste. Disse sammenkædede lister indeholder de toppunkter, der har kanter med indeksets toppunkt.
Her er et eksempel på en tilstødende liste:
Lad os sige, at en graf indeholder V antal hjørner og E antal kanter.
Generelt vil rummets kompleksitet være O(V + E).
Værst tænkelige pladskompleksitet vil være O(V2) hvis den givne graf er den komplette graf
Adjacency Matrix
Adjacency Matrix består af et 2D-array. En graf med et V-antal toppunkter, vil størrelsen af matrixen være VxV.
Sige, matrix[i][j] = 5. Det betyder, at der er en kant mellem node i og j, hvor vægten er 5.
Lad os se på følgende graf og dens Adjacency-matrix:
Vi oprettede 2D-array ved at bruge disse trin:
Trin 1) Toppunkt A har en direkte kant med B, og vægten er 5. Så cellen i række A og kolonne B vil være fyldt med 5. Resten af cellerne i række A vil være fyldt med nul.
Trin 2) Toppunkter B har en direkte kant med C, og vægten er 4. Så cellen i række B og kolonne C vil være fyldt med 4. De resterende celler i række B vil blive fyldt med nul, da B ikke har nogen udgående kant til evt. andre noder.
Trin 3) Toppunkter C har ingen direkte kanter med andre hjørner. Så række C vil være fyldt med nuller.
Trin 4) Top D har en rettet kant med A og C.
- Her vil cellen i række D og kolonne A have værdien 7. Celler i række D og kolonne C vil have værdien 2.
- Resten af cellerne i række D vil være fyldt med nuller.
Trin 5) Hjørnerne E har en rettet kant med B og D. Cellen i række E og kolonne B vil have en værdi på 6. Celler i række E og kolonne D vil have en værdi på 3. Resten af cellerne i række D vil være fyldt med nuller.
Her er nogle punkter at bemærke:
- Grafen har ingen selvløkker, når den primære diagonal af tilstødende matrix er 0.
- Grafen er en rettet graf, hvis indekserne (a,b) og (b,a) ikke har samme værdi. Ellers er grafen en rettet graf.
- Grafen vil være en vægtet graf, hvis værdien af cellerne er mere end 1.
Der er et eller andet problem med tilstødende matrix, da den kræver kvadratiske mellemrum. Her gemmer vi de kanter, der ikke er forbundet. Disse kanter tildeler plads i hukommelsen.
For eksempel, hvis vi har en graf med 100 noder, så skal der 10 tusinde celler til for at gemme den i RAM. Med færre kanter i grafen kan det være spild at allokere så stor hukommelse. Så pladskompleksiteten ved hjælp af Adjacency-matricen vil være O(N2), hvor N betyder antallet af noder i grafen.
