Adjacency List og Matrise Representation of Graph
Sarah Chen
⚡ Smart oppsummering
Adjacensliste og matriserepresentasjon av grafer lagrer noder og kanter i minnet, slik at algoritmer kan krysse nettverk. Adjacensliste bruker koblede lister per node, mens adjacensmatrise bruker et kvadratisk todimensjonalt rutenett.
Selv om de ser forskjellige ut, alle sammen typer grafer kan representeres på en lignende måte. Det finnes vanligvis to typer grafrepresentasjon:
- Adjacency Matrix
- Tilknytningsliste
Tilknytningsliste
En tilstøtende liste består av lenkede lister. Hvert hjørne regnes som en matriseindeks, og hvert element representerer en lenket liste. Disse lenkede listene inneholder hjørnene som deler en kant med indeksknutepunktet.
Her er et eksempel på en liste over tilstøtende steder:
La en graf inneholde V antall hjørner og E antall kanter. Romkompleksiteten til adjacenslisten er O(V + E), som skalerer med antall reelle kanter i stedet for alle mulige par av hjørner.
Verst tenkelige romkompleksitet blir O(V²) hvis den gitte grafen er en fullstendig graf, siden hvert hjørne da er koblet til alle andre hjørner.
Adjacency Matrix
En adjacensmatrise er satt sammen av en 2D-matrise. For en graf med V hjørner vil størrelsen på matrisen være V × V.
Si matrix[i][j] = 5Det betyr at det er en kant mellom node i og node j der vekten er 5.
La oss se på følgende graf og dens adjacensmatrise:
Vi bygde 2D-array ved å bruke disse trinnene:
Trinn 1) Node A har en direkte kant med B, og vekten er 5. Så cellen i rad A og kolonne B vil være fylt med 5. Resten av cellene i rad A vil være fylt med null.
Trinn 2) Node 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 bli fylt med null, siden B ikke har noen utgående kant til noen annen node.
Trinn 3) Node C har ingen direkte kanter med noen andre noder. Så rad C vil bli fylt med nuller.
Trinn 4) Node D har en rettet kant med A og C.
- Cellen i rad D og kolonne A vil ha verdien 7. Cellen i rad D og kolonne C vil ha verdien 2.
- Resten av cellene i rad D vil bli fylt med nuller.
Trinn 5) Node E har en rettet kant med B og D. Cellen i rad E og kolonne B vil ha verdien 6. Cellen i rad E og kolonne D vil ha verdien 3. Resten av cellene i rad E 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 adjacensmatrisen er 0.
- Grafen er en rettet graf hvis cellene i (a, b) og (b, a) ikke har samme verdi. Ellers er grafen ikke-rettet.
- Grafen er en vektet graf hvis verdien i en celle er større enn 1.
Hovedproblemet med adjacensmatrisen er at den krever kvadratisk plass. Selv kanter som ikke eksisterer, allokerer fortsatt celler i minnet.
Hvis vi for eksempel har en graf med 100 noder, trengs det 10 000 celler for å lagre den i RAMMed færre kanter i grafen kan det være sløsende å allokere så mye minne. Så romkompleksiteten ved bruk av adjacensmatrisen er O(N²), hvor N er antall noder i grafen.
Tilstøtende liste vs. tilstøtende matrise
Før du velger en representasjon, er det nyttig å sammenligne begge modellene side om side på tvers av operasjonene som dominerer reelle grafarbeidsbelastninger:
| Operasjon | Adjacency Matrix | Tilknytningsliste |
|---|---|---|
| Romkompleksitet | O(V²) | O(V + E) |
| Legg til et hjørne | O(V²) | O (1) |
| Legg til en kant | O (1) | O (1) |
| Fjern en kant | O (1) | O(E) |
| Sjekk om kanten (i, j) eksisterer | O (1) | O (grad av i) |
| Iterer over naboer til i | O(V) | O (grad av i) |
| Best for | Tette grafer, hyppige kantspørringer | Sparsomme grafer, traverseringstunge oppgaver |
Kort sagt, adjacensmatrise vinner på kantoppslag i konstant tid, mens adjacenslisten vinner på minne- og naboiterasjon, og det er derfor algoritmer som BFS, DFS og Dijkstra vanligvis pares med adjacenslister.
Fordeler og ulemper med grafrepresentasjon
Hver representasjon har sine egne avveininger. Å kjenne styrkene og svakhetene ved begge modellene hjelper deg med å velge den rette for problemet du løser.
Fordeler med tilstøtende matrise:
- Konstanttids O(1) kanteksistensspørringer mellom et hvilket som helst par av noder.
- Fast indeksering gjør matrisebaserte algoritmer som Floyd-Warshall og transitiv lukking enkle å implementere.
- Vektede kanter passer naturlig i en enkelt matrisecelle.
Ulemper med tilstøtende matrise:
- Sløser bort O(V²) minne når grafen er sparsom.
- Å legge til et nytt hjørne krever endring av størrelsen på hele matrisen.
- Iterering over naboer til et enkelt hjørne tar O(V) selv når hjørnet bare har få kanter.
Fordeler med tilstøtende liste:
- Bruker bare O(V + E)-minne, som er nær det reelle kantantallet i sparsomme grafer.
- Å legge til et nytt hjørne eller en ny kant er O(1).
- Traverseringsalgoritmer som BFS og DFS itererer naboer i O(grad), noe som gir total kjøretid for O(V + E).
Ulemper med tilstøtende liste:
- Å sjekke om en spesifikk kant eksisterer tar O(grader) tid i stedet for O(1).
- Cache-lokalitet er svakere fordi lenkede lister er spredt over minnet.
- Vektede kanter trenger et ledsagerfelt eller en liste over par, noe som kompliserer datastrukturen noe.
Når skal man bruke tilstøtende liste kontra tilstøtende matrise
Valg av representasjon avhenger av grafens tetthet og operasjonene du kjører oftest. Bruk denne hurtigguiden for å velge riktig struktur:
- Foretrekker adjacensmatrisen når grafen er tett (E er nær V²), når kantene sjelden endres, og når algoritmen din spør «er det en kant mellom i og j?» mange ganger.
- Foretrekker tilstøtende liste når grafen er sparsom (E er mye mindre enn V²), når hjørnet eller kantsettet vokser under utførelse, og når du krysser grafen med BFS, DFS eller Dijkstras korteste-vei-algoritme.
- Foretrekker en blandet modell (tilstøtningsliste pluss et hash-sett med kanter) når du trenger både rask nabo-iterasjon og O(1) kantspørringer, på bekostning av ekstra minne.
Moderne grafbiblioteker som NetworkX og igraph bruker som standard tilstøtende lister fordi de fleste grafer i den virkelige verden – sosiale nettverk, veikart, nettsider, pakkeavhengigheter – er sparsomme og traversaltunge.
