Un lista adiacentei este o structură de date folosită pentru a reprezenta un grafic în care fiecare nod din grafic stochează o listă a vârfurilor învecinate.

Reprezentarea grafică a graficului direcționat la Lista de adiacență

Caracteristicile listei de vecinătate:

• Mărimea matricei este determinată de numărul de noduri din rețea.
• Numărul de muchii ale graficului este ușor de calculat.
• Lista de adiacență este a matrice zimțată .

Cum se construiește o listă de adiacență?

Este foarte ușor și simplu să construiți o listă de adiacență pentru un grafic, există anumiți pași indicați mai jos pe care trebuie să îi urmați:

• Creați o serie de liste legate de dimensiuni N , unde N este numărul de vârfuri din grafic.
• Creați o listă legată de vârfuri adiacente pentru fiecare vârf din grafic.
• Pentru fiecare margine (u, v) în grafic, adăugați în la lista legată de în , si adauga în la lista legată de în dacă graficul este nedirecționat altfel adăugați în la lista de în dacă este îndreptată din în la în . (În cazul graficelor ponderate stocați greutatea împreună cu conexiunile).

Aplicații ale listei de vecinătate:

• algoritmul lui Dijkstra , Latimea prima cautare , și Profunzime prima căutare utilizați liste de adiacență pentru a reprezenta grafice.
• Procesarea imaginii : Listele de adiacență pot fi folosite pentru a reprezenta relațiile de adiacență dintre pixelii dintr-o imagine.
• Dezvoltarea jocului : Aceste liste pot fi folosite pentru a stoca informații despre conexiunile dintre diferite zone sau niveluri pe care dezvoltatorii de jocuri folosesc grafice pentru a reprezenta hărți sau niveluri de joc.

Avantajele utilizării unei liste de adiacență:

• O listă de adiacență este simplă și ușor de înțeles.
• Adăugarea sau eliminarea muchiilor dintr-un grafic este rapidă și ușoară.

Dezavantajele utilizării unei liste de adiacență:

• În listele de adiacență, accesarea marginilor poate dura mai mult decât matricea de adiacență.
• Necesită mai multă memorie decât matricea de adiacență pentru grafice dense.

Ce mai poți citi?

• Sensul și definiția matricei de adjacență în DSA
• Adăugați și eliminați marginea în reprezentarea Lista de adiacență a unui grafic
• Convertiți matricea de adiacență în reprezentarea grafică a listei de adiacență
• Convertiți lista de adiacență în reprezentarea unei matrice de adiacență a unui grafic
• Comparație între lista de adiacență și reprezentarea matricei de adiacență a graficului