An läheisyysluettelo on datarakenne, jota käytetään kuvaamaan graafia, jossa jokainen graafin solmu tallentaa luettelon naapuripisteistään.
Suunnatun graafin esitys vierekkäisten kohteiden luetteloon
Naapuriluettelon ominaisuudet:
- Matriisin koko määräytyy verkon solmujen lukumäärän mukaan.
- Graafin reunojen lukumäärä on helppo laskea.
- Naapuriluettelo on a rosoinen joukko .
Kuinka rakentaa vierekkäisyysluettelo?
Graafille on erittäin helppoa ja yksinkertaista rakentaa vierekkäisyysluettelo. Alla on tiettyjä vaiheita, joita sinun on noudatettava:
- Luo joukko linkitettyjä luetteloita N , jossa N on graafin kärkien lukumäärä.
- Luo linkitetty luettelo vierekkäisistä pisteistä jokaiselle graafin kärjelle.
- Jokaiselle reunalle (u, v) lisää kaavioon sisään linkitettyyn luetteloon sisään , ja lisää sisään linkitettyyn luetteloon sisään jos kuvaaja on suuntaamaton, muuten lisää sisään luetteloon sisään jos se on suunnattu sisään to sisään . (Painotettujen kaavioiden tapauksessa tallenna paino liitäntöjen kanssa).
Läheisyysluettelon sovellukset:
- Dijkstran algoritmi , Leveys ensimmäinen haku , ja Syvyys ensimmäinen haku käytä vierekkäisyysluetteloita kuvaamaan kuvaajia.
- Kuvankäsittely : Vierekkäisyysluetteloita voidaan käyttää kuvaamaan kuvan pikselien välisiä vierekkäisyyssuhteita.
- Pelin kehitys : Näihin luetteloihin voidaan tallentaa tietoja eri alueiden tai tasojen välisistä yhteyksistä, joita pelinkehittäjät käyttävät kaavioita esittämään pelin karttoja tai tasoja.
Vierekkäisyysluettelon käytön edut:
- Vierekkäisyysluettelo on yksinkertainen ja helppo ymmärtää.
- Reunojen lisääminen tai poistaminen graafista on nopeaa ja helppoa.
Vierekkäisyysluettelon käytön haitat:
- Vierekkäisyysluetteloissa reunoihin pääseminen voi kestää kauemmin kuin viereisyysmatriisin.
- Se vaatii enemmän muistia kuin vierekkäisyysmatriisi tiheille kaavioille.
Mitä muuta voit lukea?
- Vierekkäisyysmatriisin merkitys ja määritelmä DSA:ssa
- Lisää ja poista reuna graafin vierekkäisyysluettelossa
- Muunna Graafin vierekkäisyysmatriisi vierekkäisyysluetteloesitykseen
- Muunna vierekkäisyysluettelo graafin vierekkäisyysmatriisiesitykseen
- Graafin vierekkäisyysluettelon ja vierekkäisyysmatriisiesityksen vertailu