Adjacency List och Matrix Representation of Graph
Sarah Chen
⚡ Smart sammanfattning
Adjacenslista och matrisrepresentation av grafer lagrar noder och kanter i minnet, vilket gör att algoritmer kan korsa nätverk. Adjacenslista använder länkade listor per nod medan adjacensmatriser använder ett kvadratiskt tvådimensionellt rutnät.
Även om de ser olika ut, alla typer av grafer kan representeras på ett liknande sätt. Det finns generellt två typer av grafrepresentation:
- Adjacency matris
- Angränsningslista
Angränsningslista
En adjacenslista består av länkade listor. Varje nodpunkt betraktas som ett arrayindex, och varje element representerar en länkad lista. Dessa länkade listor innehåller de noder som delar en kant med indexnoden.
Här är ett exempel på en angränsningslista:
Låt en graf innehålla V antal noder och E antal kanter. Rumskomplexiteten för adjacenslistan är O(V + E), som skalas med antalet reella kanter snarare än alla möjliga par av noder.
Värsta tänkbara rymdkomplexitet blir O(V²) om den givna grafen är en komplett graf, eftersom varje nodpunkt sedan ansluter till varje annan nodpunkt.
Adjacency matris
En adjacentmatris består av en 2D-matris. För en graf med V noder blir matrisens storlek V × V.
Säga matrix[i][j] = 5Det betyder att det finns en kant mellan nod i och nod j där vikten är 5.
Låt oss titta på följande graf och dess adjacentmatris:
Vi byggde 2D-array med dessa steg:
Steg 1) Punkt A har en rak 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) Nod B har en rak 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 annan nod.
Steg 3) Punkt C har inga direkta kanter med några andra noder. Så rad C kommer att fyllas med nollor.
Steg 4) Vertex D har en riktad kant med A och C.
- Cellen i rad D och kolumn A kommer att ha värdet 7. Cellen 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) Punkt E har en riktad kant med B och D. Cellen i rad E och kolumn B kommer att ha värdet 6. Cellen i rad E och kolumn D kommer att ha värdet 3. Resten av cellerna i rad E kommer att fyllas med nollor.
Här är några punkter att lägga märke till:
- Grafen har inga självloopar när den primära diagonalen för adjacentmatrisen är 0.
- Grafen är en riktad graf om cellerna vid (a, b) och (b, a) inte har samma värde. Annars är grafen oriktad.
- Grafen är en viktad graf om värdet i någon cell är större än 1.
Det största problemet med adjacentmatrisen är att den kräver kvadratiskt utrymme. Även kanter som inte existerar allokerar fortfarande celler i minnet.
Om vi till exempel har en graf med 100 noder, behövs 10 000 celler för att lagra den i RAMMed färre kanter i grafen kan allokering av så mycket minne vara slöseri. Så rymdkomplexiteten med hjälp av adjacentmatrisen är O(N²), där N är antalet noder i grafen.
Angränsningslista vs. Angränsningsmatris
Innan man väljer en representation är det bra att jämföra båda modellerna sida vid sida över de operationer som dominerar verkliga grafarbetsbelastningar:
| Operation | Adjacency matris | Angränsningslista |
|---|---|---|
| Rymdkomplexitet | O(V²) | O(V + E) |
| Lägg till ett hörn | O(V²) | O (1) |
| Lägg till en kant | O (1) | O (1) |
| Ta bort en kant | O (1) | O(E) |
| Kontrollera om kanten (i, j) existerar | O (1) | O (grad av i) |
| Iterera över grannar till i | O (V) | O (grad av i) |
| Bäst för | Täta grafer, frekventa kantfrågor | Glesa grafer, traverseringstunga uppgifter |
Kort sagt vinner adjacensmatrisen på kantsökningar i konstant tid, medan adjacenslistan vinner på minnes- och granniteration, vilket är anledningen till att algoritmer som BFS, DFS och Dijkstra vanligtvis parar ihop med adjacenslistor.
Fördelar och nackdelar med grafrepresentation
Varje representation har sina egna avvägningar. Att känna till styrkorna och svagheterna hos båda modellerna hjälper dig att välja rätt modell för det problem du löser.
Fördelar med adjacency-matris:
- Konstanttids-O(1) kantexistensfrågor mellan valfritt par av noder.
- Fast indexering gör matrisbaserade algoritmer som Floyd-Warshall och transitiv stängning enkla att implementera.
- Viktade kanter passar naturligt i en enda matriscell.
Nackdelar med adjacency-matris:
- Slösar bort O(V²) minne när grafen är gles.
- Att lägga till ett nytt hörn kräver att hela matrisen ändras i storlek.
- Iterering över grannar till en enda vertex tar O(V) även när vertexen bara har ett fåtal kanter.
Fördelar med angränsningslista:
- Använder endast O(V + E)-minne, vilket ligger nära det verkliga kantantalet i glesa grafer.
- Att lägga till en ny hörn eller kant är O(1).
- Traversalalgoritmer som BFS och DFS itererar grannar i O(grad), vilket ger den totala körtiden för O(V + E).
Nackdelar med angränsningslista:
- Att kontrollera om en specifik kant existerar tar O(grader) tid istället för O(1).
- Cache-lokaliteten är svagare eftersom länkade listor är utspridda över minnet.
- Viktade kanter behöver ett kompletterande fält eller en lista med par, vilket komplicerar datastrukturen något.
När man ska använda en adjacency-lista kontra en adjacency-matris
Valet av representation beror på grafens densitet och de operationer du kör oftast. Använd den här snabbguiden för att välja rätt struktur:
- Föredra adjacensmatrisen när grafen är tät (E är nära V²), när kanterna sällan ändras, och när din algoritm frågar "finns det en kant mellan i och j?" många gånger.
- Föredra angränsningslistan när grafen är gles (E är mycket mindre än V²), när vertex- eller kantmängden växer under exekvering, och när man passerar grafen med BFS, DFS eller Dijkstras kortaste vägalgoritm.
- Föredrar en blandad modell (adjacency-lista plus en hash-uppsättning av kanter) när du behöver både snabb granniteration och O(1) kantfrågor, på bekostnad av extra minne.
Moderna grafbibliotek som NetworkX och igraph använder som standard angränsande listor eftersom de flesta verkliga grafer – sociala nätverk, vägkartor, webbsidor, paketberoenden – är glesa och kräver mycket traversering.
