| De ruimtecomplexiteit van een gegevensstructuur van een aangrenzende lijst is O(V + E) , waar:
* V is het aantal hoekpunten (knooppunten) in de grafiek.
* E is het aantal randen in de grafiek.
Uitleg:
1. Vertices: U moet elk hoekpunt in de grafiek minstens één keer opslaan (bijvoorbeeld in een array, hashtabel of een andere structuur die is gekoppeld aan de lijst met zijn buren). Dit draagt O(V) bij aan de ruimtecomplexiteit.
2. Randen: Voor elk hoekpunt slaat u een lijst op van de aangrenzende hoekpunten (de buren). In een eenvoudige weergave wordt elke rand (of een verwijzing/wijzer naar een buur) één keer opgeslagen voor elk hoekpunt waarmee deze is verbonden. Daarom worden in totaal alle randen in de lijsten opgeslagen.
* In een ongerichte grafiek , wordt elke rand (u, v) twee keer opgeslagen:één keer in de aangrenzende lijst van hoekpunt `u` en één keer in de aangrenzende lijst van hoekpunt `v`. U bewaart dus effectief 2 * E-randen. De constante factor (2) valt echter weg in de Big O-notatie, waardoor we O(E) overhouden.
* In een gerichte grafiek , wordt elke rand (u -> v) slechts één keer opgeslagen, in de aangrenzende lijst van hoekpunt `u`. Je slaat dus E-randen op, wat zich vertaalt naar O(E).
Waarom O(V + E) belangrijk is:
* Spaarzame grafieken: Wanneer E aanzienlijk kleiner is dan V
2
(een schaarse grafiek), is de aangrenzende lijst veel ruimte-efficiënter dan de aangrenzende matrix, die een ruimtecomplexiteit heeft van O(V
2
).
* Dichte grafieken: Wanneer E dichter bij V
2
ligt (een dichte grafiek), wordt de ruimtecomplexiteit van beide representaties vergelijkbaar. De constante factoren bij de implementatie kunnen echter nog steeds een verschil maken.
Voorbeeld:
Beschouw een grafiek met 5 hoekpunten (A, B, C, D, E) en 6 randen:
* EEN <-> B
* EEN <-> C
* B <-> C
* B <-> D
* C <-> E
* D <-> E
Hier is V =5 en E =6.
De aangrenzende lijst vereist ruimte voor:
* Opslaan van de 5 hoekpunten (O(V)).
* Opslaan van de 12 verwijzingen naar buren (6 randen, elk twee keer opgeslagen omdat het een ongerichte grafiek is - O(2E) =O(E)).
Daarom is de totale ruimte O(V + E) =O(5 + 6) =O(11).
Samengevat: Aangrenzende lijsten bieden een ruimte-efficiënte manier om grafieken weer te geven, vooral dunne grafieken, omdat hun ruimtecomplexiteit lineair schaalt met het aantal hoekpunten en randen. |
