Grafiko duomenų struktūra

Turinys

Grafiko terminologija
Grafiko pavaizdavimas
Grafiko operacijos

Šioje pamokoje sužinosite, kas yra diagramos duomenų struktūra. Taip pat rasite grafiko pavaizdavimus.

Grafiko duomenų struktūra yra mazgų, turinčių duomenis ir sujungtų su kitais mazgais, rinkinys.

Pabandykime tai suprasti per pavyzdį. Feisbuke viskas yra mazgas. Tai apima vartotoją, nuotrauką, albumą, įvykį, grupę, puslapį, komentarą, istoriją, vaizdo įrašą, nuorodą, pastabą … viskas, kas turi duomenų, yra mazgas.

Kiekvienas santykis yra kraštas iš vieno mazgo į kitą. Nesvarbu, ar skelbiate nuotrauką, ar prisijungiate prie grupės, pvz., Puslapio ar pan., Šiems santykiams sukuriama nauja briauna.

Grafiko duomenų struktūros pavyzdys

Tada visas „facebook“ yra šių mazgų ir briaunų rinkinys. Taip yra todėl, kad „Facebook“ naudoja duomenų diagramos struktūrą savo duomenims saugoti.

Tiksliau, grafikas yra duomenų struktūra (V, E), kurią sudaro

V viršūnių rinkinys
Kraštų E kolekcija, vaizduojama kaip sutvarkytos viršūnių poros (u, v)

Viršūnės ir kraštai

Grafike

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

Grafiko terminologija

Papildoma : sakoma, kad viršūnė yra greta kitos viršūnės, jei yra jas jungiantis kraštas. 2 ir 3 vertikalės nėra gretimos, nes tarp jų nėra krašto.
Kelias : kraštų seka, leidžianti pereiti nuo A viršūnės iki B viršūnės, vadinama keliu. 0-1, 1-2 ir 0-2 yra keliai nuo 0 viršūnės iki 2 viršūnės.
Nukreiptasis grafikas : grafikas, kuriame kraštas (u, v) nebūtinai reiškia, kad yra ir kraštas (v, u). Tokio grafiko kraštai vaizduojami rodyklėmis, kad būtų rodoma krašto kryptis.

Grafiko pavaizdavimas

Grafikai paprastai vaizduojami dviem būdais:

1. Adjacency Matrix

Gretimybės matrica yra 2D V x V viršūnių masyvas. Kiekviena eilutė ir stulpelis reiškia viršūnę.

Jei kurio nors elemento a(i)(j)reikšmė yra 1, tai reiškia, kad yra kraštas, jungiantis i ir j viršūnes.

Aukščiau sukurto grafiko gretimumo matrica yra

Grafiko gretimumo matrica

Kadangi tai yra nenukreiptas grafikas, kraštui (0,2) taip pat reikia pažymėti kraštą (2,0); gretimumo matricą paverčiant simetriška įstrižainės atžvilgiu.

Briaunų peržiūra (tikrinant, ar tarp A ir B viršūnių yra briauna) yra labai greita gretimumo matricos vaizde, tačiau turime rezervuoti vietos kiekvienam įmanomam ryšiui tarp visų viršūnių (V x V), todėl tam reikia daugiau vietos.

2. Adjacency sąrašas

Gretimybių sąrašas rodo grafiką kaip susietų sąrašų masyvą.

Masyvo indeksas žymi viršūnę, o kiekvienas jo susieto sąrašo elementas žymi kitas viršūnes, kurios sudaro viršūnės kraštą.

Pirmame pavyzdyje sudaryto grafiko gretimybių sąrašas yra toks:

Adjacency sąrašo atstovavimas

Gretimybių sąrašas yra efektyvus saugojimo požiūriu, nes mums reikia saugoti tik kraštų vertes. Grafikui su milijonais viršūnių tai gali reikšti daug sutaupytos vietos.