naapuriluettelona

Naapuriluettelona on suomenkielinen termi, jota käytetään kuvaamaan graafin naapurien listamenetelmää, eli adjacency list -rakennetta. Käytännössä jokaiselle solmulle tallennetaan lista sen naapurisolmuista. Näin graafi esitetään tiedon rakenteena, jossa yhteyksiä hallitaan solmu kerrallaan eikä kaikista mahdollisista yhteyksistä yhtä suurta neliöa.

Naapuriluettelon keskeinen idea on tilansäästö: erityisesti harvaan graafiin käytettynä se tarvitsee muistia O(V + E), missä V on solmujen määrä ja E on kaarien määrä. Tämä eroaa adjakointimatriisasta, joka vie tilaa O(V^2). Naapuriluettelona sopii hyvin dynaamisiin verkkoihin, joissa kaaret voivat muuttua, koska lisäysten ja poistojen toteuttaminen on yleensä suoraviivaista, usein lähes O(1) aikavetoja operaatioita varten, riippuen käytetystä rakenteesta (kaksisuuntaiset listat, hash-taulut jne.).

Rajoitteet ja variantit: adjacencylists voidaan tallentaa esimerkiksi dynaamisina linkitettyinä listoina tai indeksoituna taulukkomuodossa. Suuntautuneessa graafissa jokaisella solmulla on oma lista pään naapurista, kun taas kaksisuuntaisessa graafissa kumpikin suunta tarvitsee oman listansa. Moni- tai painoarvoiset kaaret voidaan sisällyttää listaesineisiin, jolloin kunkin naapurilistan alussa tai lisänä on kaaren paino.

Käyttökohteita ovat muun muassa verkko- ja reititysalgoritmit, sosiaaliset verkostot, GIS-sovellukset sekä monimutkaisten verkkojen simuloinnit. Esimerkkinä pienellä graafilla solmuille 1–4 naapurilistat voivat olla: 1: 2,3; 2: 1,4; 3: 1; 4: 2.