Rumkompleksiteten af en adjacency -liste Datastruktur er
O (V + E) , hvor:
* v er antallet af vertices (noder) i grafen.
* e er antallet af kanter i grafen.
Forklaring:
1. vertices: Du skal opbevare hvert toppunkt i grafen mindst en gang (f.eks. I en matrix, hash -tabel eller en anden struktur, der kortlægger listen over sine naboer). Dette bidrager med O (v) til rumkompleksiteten.
2. kanter: For hvert toppunkt gemmer du en liste over dets tilstødende vertikater (dens naboer). I en simpel repræsentation gemmes hver kant (eller en reference/markør til en nabo) én gang for hvert toppunkt, den er forbundet til. Derfor opbevares alle kanter i alt på listerne.
* I en ikke -rettet graf , hver kant (u, v) gemmes to gange:en gang på adjacency -listen over toppunktet `u` og en gang på adjacency -listen over toppunktet` V`. Så du vil effektivt opbevare 2 * e kanter. Imidlertid falder den konstante faktor (2) i stor O -notation, hvilket efterlader os med O (E).
* I en rettet graf , hver kant (u -> v) gemmes kun én gang i adjacency -listen over toppunktet `u '. Så du opbevarer E -kanter, der oversættes til O (E).
hvorfor O (v + e) er vigtig:
* sparsomme grafer: Når E er markant mindre end V
2
(En sparsom graf), Adjacency-listen er meget mere pladseffektiv end adjacency-matrixen, der har en rumkompleksitet af O (v
2
).
* Tæt grafer: Når E er tættere på V
2
(En tæt graf), rumkompleksiteten af begge repræsentationer bliver ens. Imidlertid kan de konstante faktorer i implementeringen stadig gøre en forskel.
Eksempel:
Overvej en graf med 5 hjørner (A, B, C, D, E) og 6 kanter:
* A <-> b
* A <-> c
* B <-> c
* B <-> D
* C <-> e
* D <-> e
Her, V =5 og E =6.
Adjacency -listen kræver plads til:
* Opbevaring af de 5 hjørner (O (v)).
* Opbevaring af de 12 henvisninger til naboer (6 kanter, der hver er gemt to gange, fordi det er en ikke -rettet graf - O (2e) =O (E)).
Derfor er den samlede plads O (V + E) =O (5 + 6) =O (11).
Kortfattet: Adjacency-lister giver en pladseffektiv måde at repræsentere grafer på, især sparsomme grafer, da deres rumkompleksitetsskalaer lineært med antallet af vertikater og kanter.
