Graafin vierekkäisyysluettelo ja matriisiesitys

Vaikka ne näyttävätkin erilaisilta, kaikki kaavioiden tyypit voidaan esittää samalla tavalla. Graafiesitystä on yleensä kahdenlaisia:

1. Viereisyysmatriisi
2. Adjacency-luettelo

Adjacency-luettelo

Vierekkäisyysluettelo koostuu linkitetyistä luetteloista. Jokaista kärkeä pidetään taulukkoindeksinä, ja jokainen elementti edustaa linkitettyä luetteloa. Nämä linkitetyt listat sisältävät kärjet, joilla on indeksipisteen reunat.

Tässä on esimerkki vierekkäisyysluettelosta:

Oletetaan, että graafissa on V määrä pisteitä ja E määrä reunoja.

Yleensä tilan monimutkaisuus on O(V + E).

Pahimmassa tapauksessa tilan monimutkaisuus on O(V2) jos annettu Graafi on täydellinen Graafi

Viereisyysmatriisi

Vierekkäisyysmatriisi koostuu 2D-taulukosta. Graafissa, jossa on V määrä pisteitä, matriisin koko on VxV.

Sanoa, matrix[i][j] = 5. Se tarkoittaa, että solmun i ja j välillä on reuna, jossa paino on 5.

Katsotaanpa seuraavaa kuvaajaa ja sen vierekkäisyysmatriisia:

Loimme 2D-taulukko käyttämällä näitä vaiheita:

Vaihe 1) Vertikaalella A on suora reuna B:n kanssa ja paino on 5. Joten rivin A solu ja sarake B täytetään 5:llä. Muut rivin A solut täytetään nollalla.

Vaihe 2) Pisteillä B on suora reuna C:n kanssa ja paino on 4. Joten rivin B ja sarakkeen C solu täytetään 4:llä. Loput rivin B solut täytetään nollalla, koska B:llä ei ole minkään lähtevää reunaa. muut solmut.

Vaihe 3) Pisteillä C ei ole suoria reunoja muiden kärkien kanssa. Joten rivi C täytetään nollilla.

Vaihe 4) Vertikassa D on suunnattu reuna A:n ja C:n kanssa.

• Tässä rivin D ja sarakkeen A solun arvo on 7. Rivin D ja sarakkeen C solujen arvo on 2.
• Loput rivin D solut täytetään nollilla.

Vaihe 5) Pisteillä E on suunnattu reuna B:n ja D:n kanssa. Rivin E ja sarakkeen B solun arvo on 6. Rivin E ja sarakkeen D solujen arvo on 3. Muut rivin D solut ovat täynnä nollia.

Tässä on joitain huomioitavia kohtia:

• Grafissa ei ole itsesilmukoita, kun vierekkäisyysmatriisin ensisijainen diagonaali on 0.
• Graafi on suunnattu graafi, jos indekseillä (a,b) ja (b,a) ei ole sama arvo. Muussa tapauksessa Graafi on suunnattu graafi.
• Kaavio on painotettu graafi, jos solujen arvo on suurempi kuin 1.

Viereisyysmatriisissa on ongelma, koska se vaatii välilyöntejä. Täällä tallennamme reunat, joita ei ole yhdistetty. Nämä reunat varaavat tilaa muistissa.

Esimerkiksi, jos meillä on graafi, jossa on 100 solmua, tarvitaan 10 tuhatta solua sen tallentamiseen RAM. Kun kaaviossa on vähemmän reunoja, niin suuren muistin varaaminen voi olla hukkaa. Joten avaruuden monimutkaisuus vierekkäisyysmatriisia käyttämällä on O(N2), jossa N tarkoittaa kaavion solmujen määrää.