Aká je priestorová zložitosť štruktúry údajov o susednom zozname?

Vesmírna zložitosť dátovej štruktúry zoznamu susediacich zoznamov je o (v + e) ​​ , kde:

* v je počet vrcholov (uzlov) v grafe.

* e je počet hrán v grafe.

Vysvetlenie:

1. vrcholy: Musíte ukladať každý vrchol v grafe aspoň raz (napr. V poli, hashova tabuľka alebo iná štruktúra, ktorá mapuje na zoznam svojich susedov). To prispieva O (v) k zložitosti vesmíru.

2. hrany: Pre každý vrchol uložíte zoznam svojich susedných vrcholov (jeho susedov). V jednoduchej reprezentácii sa každá hrana (alebo referencia/ukazovateľ na suseda) uloží raz pre každý vrchol, ku ktorému je pripojený. Preto sú všetky hrany uložené v zoznamoch.

* V nezasmerovanom grafe , každá hrana (u, v) bude uložená dvakrát:raz v zozname susedných osôb `u` a raz v zozname advokátov vrcholu` V`. Takže efektívne uložíte 2 * E hrán. Konštantný faktor (2) sa však vynecháva vo veľkej notácii a zanecháva nám o (e).

* V grate s , každá hrana (u -> v) je uložená iba raz, v zozname susedných osôb `u`. Takže budete ukladať hrany E, ktoré sa prekladajú do O (e).

Prečo je O (v + e) ​​dôležité:

* riedke grafy: Keď je e výrazne menší ako V ^{2 (riedky graf), zoznam susedných síl je oveľa priestorovo efektívnejší ako matica susediacej matice, ktorá má priestorovú zložitosť O (V}

2 ).

* husté grafy: Keď je e bližšie k V

2 (hustý graf), priestorová zložitosť oboch reprezentácií sa stáva podobnou. Konštantné faktory v implementácii však môžu stále zmeniť.

Príklad:

Zoberme si graf s 5 vrcholmi (A, B, C, D, E) a 6 okrajmi:

* A <--> b

* A <--> c

* B <--> c

* B <--> d

* C <--> e

* D <--> e

Tu, v =5 a e =6.

Zoznam susedstva by vyžadoval priestor pre:

* Uloženie 5 vrcholov (O (v)).

* Ukladanie 12 odkazov na susedov (6 hrán, z ktorých každá je uložená dvakrát, pretože je to nepriamy graf - o (2e) =o (e)).

Preto je celkový priestor O (v + e) ​​=o (5 + 6) =o (11).

v súhrne: Zoznamy susedstva poskytujú priestorovo efektívny spôsob, ako reprezentovať grafy, najmä riedke grafy, pretože ich priestorová zložitosť lineárne mierky s počtom vrcholov a hrán.

• Predchádzajúca strana: Aký je význam kompresie údajov v kontextovej správe a optimalizácii digitálnych informácií? 
• Ďalšia strana: Aká je časová zložitosť operácie vektorového vloženia do dátových štruktúr a algoritmov?