Die Raumkomplexität einer Adjazenzlistendatenstruktur beträgt
o (V + E) , Wo:
* v ist die Anzahl der Eckpunkte (Knoten) in der Grafik.
* e ist die Anzahl der Kanten in der Grafik.
Erläuterung:
1. Eckpunkte: Sie müssen jeden Scheitelpunkt mindestens einmal in der Grafik speichern (z. B. in einer Array-, Hash -Tabelle oder einer anderen Struktur, die der Liste seiner Nachbarn ordnet). Dies trägt O (v) zur Raumkomplexität bei.
2. Kanten: Für jeden Scheitelpunkt speichern Sie eine Liste der angrenzenden Scheitelpunkte (seine Nachbarn). In einer einfachen Darstellung wird jede Kante (oder ein Referenz/Zeiger auf einen Nachbarn) für jeden Scheitelpunkt, an den er verbunden ist, einmal gespeichert. Insgesamt werden alle Kanten in den Listen gespeichert.
* In einem ungerichteten Graph , jede Kante (u, v) wird zweimal gespeichert:einmal in der Adjazenzliste von Scheitelpunkten `u` und einmal in der Adjazenzliste von Scheitelpunkt` v`. Sie werden also effektiv 2 * E -Kanten speichern. Der konstante Faktor (2) wird jedoch in der Big O -Notation fallen und lässt uns mit O (e) zurück.
* In a gerichteten Grafik , jede Kante (u -> v) wird nur einmal in der Adjazenzliste von Vertex `u` gespeichert. Sie werden also E -Kanten speichern, was zu O (e) führt.
Warum O (V + E) wichtig ist:
* Spärliche Graphen: Wenn E signifikant kleiner als V 2
ist (Ein spärliches Diagramm) Die Adjazenzliste ist viel platzeffizienter als die Adjazenzmatrix, die eine Raumkomplexität von O aufweist (V
2
).
* dichte Graphen: Wenn E näher an V
2
ist (Eine dichte Grafik), die Raumkomplexität beider Darstellungen wird ähnlich. Die konstanten Faktoren in der Implementierung können jedoch immer noch einen Unterschied machen.
Beispiel:
Betrachten Sie einen Diagramm mit 5 Scheitelpunkten (A, B, C, D, E) und 6 Kanten:
* A <-> b
* A <-> c
* B <-> c
* B <-> D.
* C <-> e
* D <-> e
Hier, v =5 und e =6.
Die Adjazenzliste würde Platz für:
* Speichern Sie die 5 Scheitelpunkte (o (v)).
* Speichern Sie die 12 Verweise auf Nachbarn (6 Kanten, die jeweils zweimal gespeichert sind, weil es sich um ein ungerichtes Diagramm handelt - o (2e) =o (e)).
Daher ist der Gesamtraum o (v + e) =o (5 + 6) =o (11).
Zusammenfassend: Adjazenzlisten bieten eine platzeffiziente Möglichkeit, Grafiken, insbesondere spärliche Graphen, darzustellen, da ihre Raumkomplexität linear mit der Anzahl der Eckpunkte und Kanten skaliert wird.
