Adjacency List och Matrix Representation of Graph

Även om de ser olika ut, alla typer av grafer kan representeras på liknande sätt. Det finns i allmänhet två typer av grafrepresentation:

1. Adjacency matris
2. Angränsningslista

Angränsningslista

Adjacency List består av länkade listor. Varje vertex betraktas som ett arrayindex, och varje element representerar en länkad lista. Dessa länkade listor innehåller de hörn som har kanter med indexpunkten.

Här är ett exempel på en angränsande lista:

Låt oss säga att en graf innehåller V antal hörn och E antal kanter.

I allmänhet kommer utrymmets komplexitet att vara O(V + E).

Värsta tänkbara utrymmeskomplexitet kommer att vara O(V2) om den givna grafen är den fullständiga grafen

Adjacency matris

Adjacency Matrix består av en 2D-array. En graf som har ett V-antal hörn, kommer storleken på matrisen att vara VxV.

Säga, matrix[i][j] = 5. Det betyder att det finns en kant mellan nod i och j där vikten är 5.

Låt oss titta på följande graf och dess närliggande matris:

Vi skapade 2D-array med dessa steg:

Steg 1) Topp A har en direkt kant med B, och vikten är 5. Så cellen i rad A och kolumn B kommer att fyllas med 5. Resten av cellerna i rad A kommer att fyllas med noll.

Steg 2) Hörnen B har en direkt kant med C, och vikten är 4. Så cellen i rad B och kolumn C kommer att fyllas med 4. De återstående cellerna i rad B kommer att fyllas med noll eftersom B inte har någon utgående kant till någon andra noder.

Steg 3) Hörnen C har inga direkta kanter med några andra hörn. Så rad C kommer att fyllas med nollor.

Steg 4) Vertices D har en riktad kant med A och C.

• Här kommer cellen i rad D och kolumn A att ha värdet 7. Celler i rad D och kolumn C kommer att ha värdet 2.
• Resten av cellerna i rad D kommer att fyllas med nollor.

Steg 5) Vertices E har en riktad kant med B och D. Cellen i rad E och kolumn B kommer att ha värdet 6. Celler i rad E och kolumn D kommer att ha värdet 3. Resten av cellerna i rad D kommer att vara fylld med nollor.

Här är några punkter att lägga märke till:

• Grafen har inga självslingor när den primära diagonalen för närliggande matris är 0.
• Grafen är en riktad graf om indexen (a,b) och (b,a) inte har samma värde. Annars är grafen en riktad graf.
• Grafen kommer att vara en viktad graf om värdet på cellerna är mer än 1.

Det finns några problem med närliggande matris eftersom den kräver kvadratiska mellanslag. Här lagrar vi kanterna som inte är sammankopplade. Dessa kanter allokerar utrymme i minnet.

Till exempel, om vi har en graf med 100 noder, behövs 10 tusen celler för att lagra den i RAM. Med färre kanter i grafen kan det vara ett slöseri att allokera så stort minne. Så rymdkomplexiteten med hjälp av Adjacency-matrisen kommer att vara O(N2), där N betyder antalet noder i grafen.