Adjacency List og Matrise Representation of Graph

Selv om de ser forskjellige ut, alle sammen typer grafer kan representeres på lignende måte. Det er generelt to typer grafrepresentasjon:

1. Adjacency Matrix
2. Tilknytningsliste

Tilknytningsliste

Adjacency List består av Linked Lists. Hvert toppunkt betraktes som en matriseindeks, og hvert element representerer en koblet liste. Disse koblede listene inneholder toppunktene som har kanter med indeksens toppunkt.

Her er et eksempel på en tilstøtende liste:

La oss si at en graf inneholder V antall hjørner og E antall kanter.

Generelt vil plasskompleksiteten være O(V + E).

Det verste tilfellet vil være kompleksitet O(V2) hvis den gitte grafen er den komplette grafen

Adjacency Matrix

Adjacency Matrix består av en 2D-array. Graf som har et V-antall toppunkter, vil størrelsen på matrisen være VxV.

Si, matrix[i][j] = 5. Det betyr at det er en kant mellom node i og j der vekten er 5.

La oss se på følgende graf og dens Adjacency-matrise:

Vi opprettet 2D-array ved å bruke disse trinnene:

Trinn 1) Toppunkt A har en direkte kant med B, og vekten er 5. Så cellen i rad A og kolonne B vil bli fylt med 5. Resten av cellene i rad A vil bli fylt med null.

Trinn 2) Toppunktene B har en direkte kant med C, og vekten er 4. Så cellen i rad B og kolonne C vil bli fylt med 4. De resterende cellene i rad B vil fylles med null da B ikke har noen utgående kant til noen andre noder.

Trinn 3) Toppunktene C har ingen direkte kanter med andre toppunkter. Så rad C vil bli fylt med nuller.

Trinn 4) Toppunkt D har en rettet kant med A og C.

• Her vil cellen i rad D og kolonne A ha verdien 7. Cellene i rad D og kolonne C vil ha verdien 2.
• Resten av cellene i rad D vil bli fylt med nuller.

Trinn 5) Toppunktene E har en rettet kant med B og D. Cellen i rad E og kolonne B vil ha en verdi på 6. Celler i rad E og kolonne D vil ha en verdi på 3. Resten av cellene i rad D vil være fylt med nuller.

Her er noen punkter å legge merke til:

• Grafen har ingen selvløkker når den primære diagonalen til tilstøtende matrisen er 0.
• Grafen er en rettet graf hvis indeksene (a,b) og (b,a) ikke har samme verdi. Ellers er grafen en rettet graf.
• Grafen vil være en vektet graf hvis verdien av cellene er mer enn 1.

Det er et problem med tilstøtende matrisen da den krever kvadratiske mellomrom. Her lagrer vi kantene som ikke er koblet sammen. Disse kantene tildeler plass i minnet.

For eksempel, hvis vi har en graf med 100 noder, trengs 10 tusen celler for å lagre den i RAM. Med færre kanter i grafen kan det være bortkastet å allokere så stort minne. Så plasskompleksiteten ved å bruke Adjacency-matrisen vil være O(N2), der N betyr antall noder i grafen.