Pozdravljeni vsi.
V tem zapisu sem se odločil našteti glavne podatkovne strukture, ki se uporabljajo za shranjevanje grafov v računalništvu, spregovoril pa bom še o nekaj takšnih strukturah, ki so se mi nekako »izkristalizirale«.
Torej, začnimo. Ampak ne od samega začetka – mislim, da vsi že vemo, kaj je graf in kaj so (usmerjeni, neusmerjeni, uteženi, neuteženi, z ali brez več robov in zank).
Torej, gremo. Kakšne možnosti podatkovnih struktur za »shranjevanje grafov« imamo?
1. Matrične podatkovne strukture
1.1 Matrika sosednosti. Matrika sosednosti je matrika, kjer naslovi vrstic in stolpcev ustrezajo številu točk grafa, vrednost vsakega od njegovih elementov a(i,j) pa je določena s prisotnostjo ali odsotnostjo robov med točkami. i in j (jasno je, da bo za neusmerjen graf takšna matrika simetrična ali pa se lahko dogovorimo, da vse vrednosti shranimo samo nad glavno diagonalo). Za neutežene grafe lahko a(i,j) nastavimo s številom robov od i do j (če takega roba ni, potem je a(i,j)= 0), za utežene grafe pa tudi s težo (skupna teža) omenjenih robov.
1.2 Matrika pojavnosti. V tem primeru je naš graf shranjen tudi v tabeli, v kateri številke vrstic praviloma ustrezajo številkam njenih oglišč, številke stolpcev pa vnaprej oštevilčenim robom. Če sta vozlišče in rob incidentna drug drugemu, potem je v ustrezno celico zapisana vrednost, ki ni nič (za neusmerjene grafe je 1 zapisano, če sta vozlišče in rob incidentna, za usmerjene grafe - "1", če rob "izstopa" iz oglišča in "-1", če "vključuje" vanj (to je dovolj enostavno zapomniti, ker se zdi, da je tudi znak "minus" "vključen" v število "-1")). Za utežene grafe lahko spet namesto 1 in -1 določite skupno težo roba.
2. Podatkovne strukture naštevanja
2.1 Seznam sosedov. No, tukaj se zdi, da je vse preprosto. Vsako vozlišče grafa lahko na splošno povežemo s poljubno oštevilčevalno strukturo (seznam, vektor, niz, ...), ki bo shranila številke vseh vozlišč, ki mejijo na dano. Pri usmerjenih grafih bomo na tak seznam dodali le tista vozlišča, do katerih obstaja “usmerjen” rob iz značilnega vozlišča. Za utežene grafe bo izvedba bolj zapletena.
2.2 Seznam reber. Precej priljubljena podatkovna struktura. Seznam robov, kot nam pove Captain Obviousness, je pravzaprav seznam robov grafa, od katerih je vsak določen z začetnim ogliščem, končnim ogliščem (za neusmerjene grafe vrstni red tukaj ni pomemben, čeprav lahko za poenotenje uporabite različna pravila, na primer določanje vozlišč v naraščajočem vrstnem redu) in težo (samo za utežene grafe).
Zgoraj navedene sezname matrik si lahko ogledate podrobneje (in z ilustracijami), na primer, .
2.3 Sosednji niz. Ni najpogostejša struktura. V svojem jedru je oblika "pakiranja" sosednjih seznamov v eno oštevilčevalno strukturo (niz, vektor). Prvih n (glede na število točk grafa) elementov takšne matrike vsebuje začetne indekse iste matrike, izhajajoč iz katerih so v vrsto zapisana vsa sosednja oglišča dani.
Tukaj sem našel najbolj razumljivo (zase) razlago:
3. Vektor sosednosti in asociativni niz sosednosti
Izkazalo se je, da je avtor teh vrstic, ki ni bil profesionalni programer, ampak se je občasno ukvarjal z grafi, najpogosteje obravnaval sezname robov. Pravzaprav je priročno, če ima graf več zank in robov. In tako, pri razvoju klasičnih seznamov robov, predlagam, da smo pozorni na njihov "razvoj/vejo/modifikacijo/mutacijo", in sicer: vektor sosednosti in asociativno polje sosednosti.
3.1 Vektor sosednosti
Primer (a1): neuteženi graf
Vektor sosednosti za neuteženi graf bomo imenovali urejen niz sodega števila celih števil (a[2i], a[2i+1],..., kjer je i oštevilčen c 0), v katerem je vsak par števil je a[2i], a[2i+1] podaja rob grafa med vozliščema a[2i] oziroma a[2i+1].
Ta oblika zapisa ne vsebuje informacije o tem, ali je graf usmerjen (možni sta obe možnosti). Pri uporabi formata digrafa velja, da je rob usmerjen od a[2i] do a[2i+1]. Tukaj in spodaj: za neusmerjene grafe se po potrebi lahko uporabijo zahteve za vrstni red zapisovanja vozlišč (na primer, da je na prvem mestu vozlišče z nižjo vrednostjo števila, ki mu je dodeljeno).
V C++ je priporočljivo podati sosednji vektor z uporabo std::vector, od tod tudi ime te podatkovne strukture.
Primer (a2): neutežen graf, uteži robov so celo število
Po analogiji s primerom (a1) imenujemo vektor sosednosti za uteženi graf s celoštevilskimi utežmi robov urejen niz (dinamično polje) števil (a[3i], a[3i+1], a[3i+2], ..., kjer je i oštevilčen c 0), kjer vsak "trojček" števil a[3i], a[3i+1], a[3i+2] določa rob grafa med vozlišči, oštevilčenimi a[3i] oziroma a[3i+1], vrednost a [3i+2] pa je teža tega roba. Tudi tak graf je lahko usmerjen ali ne.
Primer (b): neutežen graf, neceloštevilske uteži robov
Ker je heterogenih elementov nemogoče shraniti v en niz (vektor), je na primer možna naslednja izvedba. Graf je shranjen v paru vektorjev, v katerem je prvi vektor sosednji vektor grafa brez podajanja uteži, drugi vektor pa vsebuje ustrezne uteži (možna izvedba za C++: std::pair ). Tako bo za rob, definiran s parom vozlišč pod indeksoma 2i, 2i+1 prvega vektorja, utež enaka elementu pod indeksom i drugega vektorja.
No, zakaj je to potrebno?
No, avtorju teh vrstic se je zdela precej uporabna za reševanje številnih težav. No, s formalnega vidika bodo naslednje prednosti:
- Vektor sosednosti je, tako kot katera koli druga "naštevalna" struktura, precej kompakten, zavzame manj pomnilnika kot matrika sosednosti (za redke grafe) in je relativno enostaven za implementacijo.
- Točke grafa načeloma lahko označimo tudi z negativnimi števili. Kaj pa, če je takšna "perverzija" potrebna?
- Grafi lahko vsebujejo več robov in več zank z različnimi utežmi (pozitivno, negativno, celo nič). Tu ni nobenih omejitev.
- Robom lahko dodelite tudi različne lastnosti – vendar za več o tem glejte razdelek 4.
Vendar je treba priznati, da ta "seznam" ne pomeni hitrega dostopa do roba. In tukaj na pomoč priskoči Associative Adjacency Array, ki je obravnavan spodaj.
3.2 Asociativni sosednji niz
Torej, če je dostop do določenega roba, njegove teže in drugih lastnosti kritičen za nas, pomnilniške zahteve pa nam ne dovoljujejo uporabe matrike sosednosti, potem pomislimo, kako lahko spremenimo vektor sosednosti, da rešimo to težavo. Ključ je torej rob grafa, ki ga lahko podamo kot urejen par celih števil. Kako to izgleda? Ali ni to ključ v asociativnem nizu? In če je tako, zakaj tega ne izvajamo? Imejmo asociativno polje, kjer bo vsak ključ - urejen par celih števil - povezan z vrednostjo - celim številom ali realnim številom, ki določa težo roba. V C++ je priporočljivo implementirati to strukturo na podlagi vsebnika std::map (std::map , int> ali std::map , dvojno>) ali std::multimap, če se pričakuje več robov. No, imamo strukturo za shranjevanje grafov, ki zavzame manj pomnilnika kot "matrične" strukture, lahko definira grafe z več zankami in robovi in niti nima strogih zahtev glede nenegativnosti števil vozlišč (ne vem kdo to rabi, pa vseeno).
4. Podatkovne strukture so polne, vendar nekaj manjka
In res je: pri reševanju številnih problemov bomo morda morali robom grafa dodeliti nekatere značilnosti in jih v skladu s tem shraniti. Če je mogoče te značilnosti nedvoumno reducirati na cela števila, potem je mogoče shraniti takšne "grafe z dodatnimi funkcijami" z uporabo razširjenih različic vektorja sosednosti in asociativnega niza sosednosti.
Torej, imejmo neutežen graf, za vsak rob katerega je potrebno shraniti na primer 2 dodatni funkciji, določeni s celimi števili. V tem primeru je mogoče definirati njegov vektor sosednosti kot urejen niz "parov", ampak "kvartetov" celih števil (a[2i], a[2i+1], a[2i+2], a [2i+3]…), kjer bosta a[2i+2] in a[2i+3] določila značilnosti ustreznega roba. Za graf s celoštevilskimi utežmi robov je vrstni red na splošno podoben (edina razlika bo v tem, da bodo atributi sledili teži roba in bodo določeni z elementoma a[2i+3] in a[2i+4] , sam rob pa ne bo naveden s 4, ampak s 5 urejenimi številkami). In za graf z neceloštevilskimi utežmi robov je mogoče funkcije zapisati v njegovo neuteženo komponento.
Pri uporabi asociativne sosednje matrike za grafe s celoštevilskimi utežmi robov je mogoče kot vrednost podati ne eno samo število, temveč niz (vektor) števil, ki poleg teže roba določajo vse njegove druge potrebne Lastnosti. Hkrati bo neprijetnost v primeru uteži, ki ni celo število, potreba po določitvi znaka s številom s plavajočo vejico (da, to je neprijetnost, vendar če takih znakov ni toliko in če ne Ne nastavite jih preveč “zapleteno” dvojno, potem morda ne bo nič) . To pomeni, da lahko v C++ razširjene asociativne sosednje nize definiramo takole: std::map , std::vector> ali std::map , std::vector, v katerem bo prva vrednost v "vektorju ključ-vrednost" teža roba, nato pa se nahajajo številčne oznake njegovih značilnosti.
Literatura:
O grafih in algoritmih na splošno:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algoritmi: konstrukcija in analiza, 2. izdaja: Trans. iz angleščine – M.: Založba Williams, 2011.
2. Harari Frank. Teorija grafov. M.: Mir, 1973.
Avtorjevo poročilo o tem istem vektorju in asociativnem nizu sosednosti:
3. Černouhov S.A. Vektor sosednosti in asociativni niz sosednosti kot načina za predstavitev in shranjevanje grafov / SA Chernouhov. Vektor sosednosti in zemljevid sosednosti kot podatkovne strukture za predstavitev grafa // Zbirka člankov mednarodne znanstvene in praktične konference »Problemi uvajanja rezultatov inovativnega razvoja in načini njihovega reševanja« (Saratov, 14.09.2019. september 2019). – Sterlitamak: AMI, 65, str. 69-XNUMX
Uporabni spletni viri na to temo:
4.
5.
Vir: www.habr.com