Kaaviotietorakenne

Sisällysluettelo

Kuvaajan terminologia
Kaavion esitys
Kuvaajaoperaatiot

Tässä opetusohjelmassa opit, mikä on graafin tietorakenne. Lisäksi löydät kuvaajan esitykset.

Kaaviotietorakenne on kokoelma solmuja, joilla on tietoja ja jotka on kytketty muihin solmuihin.

Yritetään ymmärtää tämä esimerkin avulla. Facebookissa kaikki on solmu. Se sisältää Käyttäjä, Valokuva, Albumi, Tapahtuma, Ryhmä, Sivu, Kommentti, Tarina, Video, Linkki, Huomautus … kaikki, jolla on tietoja, on solmu.

Jokainen suhde on reuna solmusta toiseen. Halusitpa sitten lähettää valokuvan, liittyä ryhmään, kuten sivulle, tälle suhteelle luodaan uusi reuna.

Esimerkki kaavion tietorakenteesta

Koko facebook on sitten kokoelma näistä solmuista ja reunoista. Tämä johtuu siitä, että facebook käyttää kuvaajan tietorakennetta tietojensa tallentamiseen.

Tarkemmin sanottuna kaavio on tietorakenne (V, E), joka koostuu

Kokoelma pisteitä V
Kokoelma reunoja E, edustettuna järjestettyinä kärkipareina (u, v)

Pisteet ja reunat

Kaaviossa

 V = (0, 1, 2, 3) E = ((0,1), (0,2), (0,3), (1,2)) G = (V, E)

Kuvaajan terminologia

Adjacency : Kärkipisteen sanotaan olevan toisen kärjen vieressä, jos niitä yhdistää reuna. Pisteet 2 ja 3 eivät ole vierekkäisiä, koska niiden välillä ei ole reunaa.
Polku : Reunasarjaa, jonka avulla voit siirtyä kärjestä A kärkeen B, kutsutaan poluksi. 0-1, 1-2 ja 0-2 ovat polkuja pisteestä 0 pisteeseen 2.
Suunnattu kaavio : Kuvaaja, jossa reuna (u, v) ei välttämättä tarkoita, että myös reuna (v, u) on. Tällaisen kaavion reunat on merkitty nuolilla osoittamaan reunan suunta.

Kaavion esitys

Kaaviot esitetään yleisesti kahdella tavalla:

1. Adjacency Matrix

Vierekkäisyysmatriisi on 2 x matriisi V x V -pisteistä. Jokainen rivi ja sarake edustavat kärkeä.

Jos minkä tahansa elementin arvo a(i)(j)on 1, se edustaa sitä, että kärjet i ja kärki j yhdistävät reunan.

Edellä luomamme kaavion vierekkäisyysmatriisi on

Kuvaa vierekkäisyysmatriisi

Koska se on suuntaamaton kaavio, reunalle (0,2) on merkittävä myös reuna (2,0); tekemällä vierekkäisyysmatriisi symmetriseksi diagonaalin suhteen.

Reunahaku (tarkista, onko kärjen A ja kärjen B välillä reuna) on erittäin nopea vierekkäisyysmatriisin esityksessä, mutta meidän on varattava tilaa kaikille mahdollisille linkeille kaikkien huippujen välillä (V x V), joten se vaatii enemmän tilaa.

2. Adjacency-luettelo

Viereisyysluettelo edustaa kaaviota linkitettyjen luetteloiden ryhmänä.

Taulukon hakemisto edustaa kärkeä ja kukin linkitetyn luettelon elementti edustaa muita huippuja, jotka muodostavat reunan kärjen kanssa.

Ensimmäisessä esimerkissä tekemämme kaavion vierekkäisyysluettelo on seuraava:

Adjacency-luettelon edustus

Viereisyysluettelo on tehokas tallennuksen kannalta, koska meidän on tallennettava vain reunojen arvot. Miljoonia pisteitä sisältävälle kuvaajalle tämä voi tarkoittaa paljon säästettyä tilaa.