reunalistojen

Reunalistat ovat graafin esitystapa, jossa jokainen reuna tallennetaan erillisenä tietueena. Yleisimmin reuna merkitään parina (u, v), jossa u ja v ovat graafin solmujen tunnisteita. Painotetuissa verkoissa reuna voidaan tallentaa kolmena tietona (u, v, w), jolloin w on reunan paino. Reunalistat soveltuvat sekä epä­suuntautettuihin että suunnattuihin graafeihin: epä­suuntautuneessa graafissa reuna voidaan tallentaa kerran (esimerkiksi u < vn), kun taas suunnatussa graafissa reuna esittää suunnattua yhteyttä (u -> v) ja voi esiintyä sekä (u, v) että (v, u) erikseen.

Rakenne ja käyttöön liittyvät ominaisuudet. Reunalista koostuu usein tavallisista pareista tai kolmikosta, jotka voidaan tallentaa peräkkäin tiedostoon tai muistissa olevaan taulukkoon. Tämä esitystapa on yksinkertainen ja kevyt, mikä tekee siitä hyvän valinnan harvaan kytkettyjen graafien tallentamiseen sekä helpon syötteenä useisiin algoritmeihin, kuten Kruskalin minitaloudelliseen puuhun. Reunalistaa voidaan lajitella tai suodattaa reunaehdoilla, mikä tukee painavien reuna-arvojen käsittelyä.

Rajoitteet. Reunalista ei ole hakkeri- tai naapuri-tietorakenteena tehokas, kun tarvitaan nopeaa naapureiden hakua tai reunan olemassaolon tarkistusta. Suoritus aika voi olla O(m) etsiessä tiettyä reunaa, ellet käytä lisästrukturia. Siksi reunalistaa käytetään usein yhdessä muiden rakenteiden kanssa tai siirretään ensin suurempi graafia kuvaava esitys.

Suhteet muihin esityksiin. Verrattuna vierekkäis-/naapurilista- ja adjacency-matriisiin, reunalista on tilatehokas erityisesti harvaan kytketyissä graafeissa ja helpompi tuottaa ja lukea tiedostoista. Reunalistojen muuntaminen toisiin esitysmuotoihin on yleisesti toteutettavissa; konversio mahdollistaa skaalautuvuuden ja eri algoritmien käytön.