naapuruusmatriisina

Naapuruusmatriisi on tapa esittää graafin naapuruussuhteet matriisimuodossa. Se on neliömäinen matriisi, jossa rivien ja sarakkeiden määrä on sama kuin graafin solmujen määrä. Matriisin jokainen alkio (i, j) kertoo, onko solmujen i ja j välillä yhteyttä eli kaarta.

Jos graafi on painottamaton, matriisin alkio on tyypillisesti 1, jos kaari on olemassa, ja 0, jos kaarta ei ole. Ohjatuissa graafeissa alkio (i, j) = 1 tarkoittaa kaarta solmusta i solmuun j. Suuntaamattomissa graafeissa matriisi on symmetrinen, eli alkio (i, j) on sama kuin alkio (j, i). Jos graafi on painotettu, matriisin alkiot voivat edustaa kaarien painoja, ja arvo 0 tai jokin muu erityinen arvo voi ilmaista kaaren puuttumista.

Naapuruusmatriisin käyttö on yleistä graafialgoritmeissa, kuten polunetsinnässä ja graafin ominaisuuksien analysoinnissa. Sen etuna on yksinkertainen toteutus ja tehokas pääsy yksittäisten solmujen naapureihin. Sen haittapuolena on kuitenkin suuri muistinkäyttö tiheissä graafeissa, joissa useimmat solmut ovat yhteydessä toisiinsa. Tällaisissa tapauksissa linkkilista saattaa olla tehokkaampi esitysmuoto.