Listă de adiacență

În teoria grafurilor și informatică, o listă de adiacență este o colecție de liste neordonate folosită pentru a reprezenta un anumit graf. Fiecare listă descrie mulțimea vecinilor unui nod din graf. Aceasta este una dintre cele mai frecvent utilizate reprezentări a grafurilor pentru utilizarea în programe de calculator.

Detalii de implementare

Graficul ilustrat mai sus are următoarea reprezentare cu listă de adiacență:
a	adiacent cu	b, c
b	adiacent cu	a, c
c	adiacent cu	a, b

O reprezentare prin listă de adiacență pentru un graf asociază fiecărui nod din graf colecția de noduri sau muchii vecine. Există mai multe variante ale acestei idei de bază, care diferă prin detaliile despre cum se implementează asocierea între noduri și colecții, prin modul în care se implementează colecțiile, dacă acestea includ atât noduri cât și muchii sau doar noduri ca obiecte de primă clasă, și prin ce tipuri de obiecte sunt folosite pentru a reprezenta nodurile și muchiile.

O implementare propusă de Guido van Rossum utilizează o tabelă hash pentru a asocia fiecărui nod dintr-un graf un tablou de noduri adiacente. În această reprezentare, un nod poate fi reprezentat prin orice hashabil. Nu există nici o reprezentare explicită a muchiilor ca obiecte.^[1]
Cormen et al. propune o implementare în care nodurile sunt reprezentate de numere de indice.^[2] Reprezentarea aceasta folosește un tablou indexat după numărul de noduri, în care celula de tablou pentru muchie conține adresa unei liste simplu înlănțuite^⁠(d) a nodurilor vecine acelui nod. În această reprezentare, nodurile listei simplu înlănțuite pot fi interpretate ca obiecte muchie; cu toate acestea, ele nu stocjează informații complete despre fiecare muchie (rețin doar unul dintre cele două capete ale muchiei) și în grafurile neorientate vor fi două noduri diferite în două liste înlănțuite separate, unul pentru fiecare muchie (câte una în fiecare listă pentru cele două capete ale muchiei).
Structura de listă de incidență orientată obiect propusă de către Goodrich și Tamassia are clase speciale de obiecte nod și obiecte muchie. Fiecare obiect nod are o variabilă de instanță care reține adresa unui obiect colecție care listează obiectele muchie vecine. La rândul lor, fiecare obiect muchie reține adresa celor două obiecte nod drept capete.^[3] Această versiune de listă adiacentă utilizează mai multă memorie decât versiunea în care nodurile adiacente sunt enumerate în mod direct, dar de obiecte muchie explicite îi permite o flexibilitate sporită la stocarea de informații suplimentare despre muchii.

Operațiuni

Principala operațiune efectuată pe structura listei de adiacență este listarea vecinilor unui anumit nod. Folosind oricare dintre exemplele de mai sus, acest lucru poate fi efectuat în timp constant pe vecin. Cu alte cuvinte, timpul total pentru a raporta toți vecinii unui nod v este proporțional cu gradul lui v.

Este de asemenea posibil, dar nu la fel de eficient, să se utilizeze liste de adiacență pentru a verifica dacă există sau nu muchie între două noduri specificate. Într-un listă de adiacență în care vecinii fiecărui nod sunt nesortați, testarea existenței unei muchii poate fi efectuată în timp proporțional cu gradul minim dintre două noduri, folosind o căutare secvențială^⁠(d) prin vecinii acestui nod. În cazul în care vecinii sunt reprezentați ca un tablou sortat, se poate utiliza căutarea binară, care necesită un timp proporțional cu logaritmul gradului.

Compromisuri

Principala alternativă la lista de adiacență este matricea de adiacență, matricea ale cărei rânduri și coloane sunt indexate după noduri și ale cărei celule conțin o valoare booleană care indică dacă există muchie între nodurile corespunzătoare rândului și coloanei celulei. Pentru un graf rar^⁠(d) (în care majoritatea perechilor de noduri nu sunt conectate prin muchii) o listă de adiacență este semnificativ mai eficientă ca spațiu decât o matrice de adiacență (stocată ca o matrice): spațiul utilizat de lista de adiacență este proporțional cu numărul de muchii și noduri din graf, în timp ce pentru o matrice de adiacență stocată în acest fel spațiul ocupat este proporțional cu pătratul numărului de noduri. Cu toate acestea, este posibilă stocarea de matrice de adiacență mult mai eficient, aproape la fel de eficient ca spațiul liniar utilizat de o listă de adiacență, prin utilizarea unui tabel hash indexat după perechile de noduri, în locul unui tablou.

Cealaltă diferență semnificativă între listele de adiacență și matricele de adiacență este eficiența operațiilor pe care le efectuează. Într-o listă de adiacență, vecinii fiecărui nod pot fi enumerați în mod eficient, în timp proporțional cu gradul nodului. Într-o matrice de adiacență, această operațiune are nevoie de timp proporțional cu numărul de noduri din graf, care poate fi semnificativ mai mare decât gradul. Pe de altă parte, matricea de adiacență permite verificarea dacă două noduri sunt adiacente reciproc, în timp constant; lista de adiacență este mai lentă în suportul oferit acestei operațiuni.

Structuri de date

Pentru utilizarea ca structură de date, principala alternativă la lista de adiacență este matricea de adiacență. Pentru că fiecare intrare în matricea de adiacență necesită doar un bit, acesta poate fi reprezentat într-un mod foarte compact, ocupând doar | V |²/8 octeți de spațiu contiguu, unde || V | este numărul de noduri din graf. Pe lângă evitarea irosirii de spațiu, această metodă de stocare încurajează localitatea referințelor.

Cu toate acestea, pentru un graf rar, listele de adiacență necesită mai puțin spațiu, pentru că nu pierd deloc spațiu pentru a reprezenta muchiile care nu sunt prezente. Folosind o implementre naivă cu tablouri pe un calculator pe 32 de biți, o listă de adiacență a unui graf neorientat are nevoie de aproximativ 2(32/8)| E | = 8| E | octeți de spațiu, unde || E | este numărul de muchii ale grafului.

Observând că un graf simplu neorientat poate avea cel mult | V |²/2 muchii, permițând și bucle, se poate nota cu d = | E |/| V |² densitatea grafului. Atunci, 8| E | > | V |²/8 , când | E |/| V |² > 1/64, adică reprezentarea prin listă de adiacență ocupă mai mult spațiu decât reprezentarea cu matrice de adiacență atunci când d > 1/64. Astfel, un graf trebuie să fie destul de rar pentru a justifica reprezentarea prin listă de adiacență.

Pe lângă compromisul de spațiu, diferite structuri de date facilitează, de asemenea, diferite operațiuni. Găsirea tuturor nodurilor adiacente la un anumit nod într-o listă de adiacență este la fel de simplă ca și parcurgerea listei. Cu o matrice de adiacență, trebuie parcurs un rând întreg, care durează un timp O(| V |). Existența unei muchiiîntre două noduri poate fi determinată imediat cu o matrice de adiacență, în timp ce cu o listă de adiacență necesită un timp proporțional cu gradul minim dintre cele două noduri.

Referințe

^ Guido van Rossum^⁠(d) (1998). „Python Patterns — Implementing Graphs”.
^ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2001). Introduction to Algorithms^⁠(d), Second Edition. MIT Press and McGraw-Hill. pp. 527–529 of section 22.1: Representations of graphs. ISBN 0-262-03293-7.
^ Michael T. Goodrich^⁠(d) and Roberto Tamassia^⁠(d) (2002). Algorithm Design: Foundations, Analysis, and Internet Examples. John Wiley & Sons. ISBN 0-471-38365-1.

Lectură suplimentară

David Eppstein^⁠(d) (1996). „ICS 161 Lecture Notes: Graph Algorithms”. Mai multe valori specificate pentru |nume= și |author= (ajutor)

Legături externe

Boost Graph Library implementează o listă de adiacență eficientă
Open Data Structures, Secțiunea 12.2, AdjacencyList: A Graph as a Collection of Lists

[1] Guido van Rossum^⁠(d) (1998). „Python Patterns — Implementing Graphs”.

[2] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2001). Introduction to Algorithms^⁠(d), Second Edition. MIT Press and McGraw-Hill. pp. 527–529 of section 22.1: Representations of graphs. ISBN 0-262-03293-7.

[A-3] Michael T. Goodrich^⁠(d) and Roberto Tamassia^⁠(d) (2002). Algorithm Design: Foundations, Analysis, and Internet Examples. John Wiley & Sons. ISBN 0-471-38365-1.

[1]

[2]

[3]