Andmestruktuurid graafide hoidmiseks: ülevaade olemasolevatest ja kaks "peaaegu uut"

Tere kõigile.

Selles märkuses otsustasin loetleda peamised andmestruktuurid, mida kasutatakse graafide salvestamiseks infotehnoloogias, samuti rääkida paarist muust struktuurist, mis on kuidagi iseendale "kristalliseerunud".

Nii et alustame. Aga mitte täiesti algusest – arvan, et teame kõik, mis on graaf ja milliseid tüüpe need on (suunatud, suunamata, kaalutud, kaalutud, mitme servaga ja silmusega või ilma).

Nii et lähme edasi. Milliseid andmestruktuuri variante graafide salvestamiseks meil on?

1. Matrilised andmestruktuurid

1.1 Naabermatriits. Sidemaatriks on maatriks, kus ridade ja veergude pealkirjad vastavad graafi tippude numbritele ning iga elemendi väärtus a(i,j) määritakse tippude i ja j vaheliste servade olemasolu või puudumise järgi (on selge, et suunamata graafi puhul on selline maatriks sümmeetriline, või siis võime kokku leppida, et kõik väärtused hoiame ainult peamise diagonaali kohal). Kaaluva graafi puhul saab a(i,j) määrata servade arvu i-st j-ni (kui sellist serva ei ole, siis a(i,j)= 0), samuti ka nende servade kaaluga (kokku kaalud).

1.2 Kande maatriks. Sellisel juhul salvestatakse meie graaf ka tabelis, kus ridadele vastavad tavaliselt graafimeetodite numbrid ja veergudele eelnevalt nummerdatud servad. Kui tipp ja serv on üksteisega külgnev, siis vastavas lahtris salvestatakse mitte-null väärtus (mitte suunatud graafide puhul kirjutatakse 1, kui tipp ja serv on külgne, suunatud graafide puhul kirjutatakse „1“, kui serv „väljub“ tipust ja „-1“, kui see „siseneb“ sellesse (seda on piisavalt lihtne meeles pidada, kuna märk „miinus“ „siseneb“ ka numbrisse „-1“)). Kaalutud graafide puhul võib samuti 1 ja -1 asemel märkida serva kogumassi.

2. Loetlevad andmestruktuurid

2.1 Naabrusloend. Siin näib kõik olevat lihtne. Iga graafi tippu saab üleüldiselt seostada mis tahes loetleva struktuuriga (loend, vektor, massiiv, …), kus hoitakse kõigi naabertippude numbreid. Suunatud graafide puhul kantakse sellesse loendisse vaid need tipud, kuhu on suunatud serv tipp-meetmest. Kaalutud graafide rakendamine on keerulisem.

2.2 Nurgareede nimekiri. Aeg-ajalt populaarne andmestruktuur. Nurgareede nimekiri, nagu ütleb Kapten Ilmselgus, on graafi nurgareede nimekiri, millest igaühel on alguspunkt, lõpppunkt (suunamata graafide puhul ei ole siinne järjestus oluline, kuigi ühtsuse nimel võib kasutada erinevaid reegleid, näiteks märkida nurgad kasvavas järjekorras) ja kaal (ainult kaalutud graafide puhul).

Ülevaatamiseks nende nimetatud nimekirjade-matriiside kohta saab lähemalt (ja illustratsioonidega) vaadata näiteks siin.

2.3 Kaudsusmassiiv. Mitte kõige sagedamini esinev struktuur. Oma olemuselt esindab see kõikide nurgareede nimekirjade andmestruktuuri „pakendamise“ vormi (massiiv, vektori). Selle massiivi esimesed n (graafi nurgade arvu järgi) elementi sisaldavad sama massiivi algindekseid, alates millest on järjestikku kirjas kõik nurgad, mis on antud nurgaga külgnevad.

Siit leidsin kõige arusaadavam (endale) selgituse: ejuo.livejournal.com/4518.html

3. Kaudsusvektor ja Assotsiatiivne kaudsusmassiiv

Nii on juhtunud, et nende ridade autor, olles mitte professionaalne programmeerija, on siiski aeg-ajalt kokku puutunud graafide ja enamasti tegeleb servade loenditega. Tõepoolest, on mugav, kui graafis on mitu silmust ja serva. Seetõttu pakun klassikaliste servade loendite arendamisel tähelepanu pöörata ka nende "arendamise/harunemise/modifitseerimise/mutatsiooni" aspektile, nimelt: naabervektorile ja naabermaatriksile.

3.1 Naabervektor

Juhtum (a1): kaalutud graaf

Kutsume naabervektoriks kaalutud graafi järjekindlat paari paaride arvu täisarve (a[2i], a[2i+1],… , kus i on nummerdatud alates 0), kus iga paar numbreid a[2i], a[2i+1] määrab graafi serva tippude vahel a[2i] ja a[2i+1] vastavalt.
See vorming ei sisalda andmeid, kas graaf on suunatud (mõlemad variandid on võimalikud). Kui seda formaati kasutatakse suunatud graafi jaoks, siis eeldatakse, et serv on suunatud a[2i] – lt a[2i+1] – le. Edasi: mitte suunatud graafide puhul võivad vajadusel olla rakendatud tippude järjekorra nõuded (näiteks, et väiksema väärtusega number oleks esimesena).

C++-s on naaberväljade vektori määramine otstarbekas std::vector abil, mis on ka põhjuseks, miks see andmestruktuuri nimi valiti.

Juhtum (a2): kaalumata graaf, servade kaalud on täisarvud.

Sarnaselt juhtumile (a1) nimetame kaalumata graafi naaberväljade vektoriks järjestatud kogumi (dünaamilise massiivi) numbreid (a[3i], a[3i+1], a[3i+2],…, kus i nummerdatakse alates 0), kus iga 'triplet' numbreid a[3i], a[3i+1], a[3i+2] määrab graafi servade vahele tippude numbritega a[3i] ja a[3i+1] vastavalt, ning väärtus a[3i+2] on selle serva kaal. Selline graaf võib olla nii suunatud kui ka mitte.

Juhtum (b): kaalumata graaf, servade kaalud ei ole täisarvud.

Kuna ühes massiivis (vektoris) ei saa hoida erinevaid elemente, siis on võimalik järgmine rakendus. Graafik salvestatakse kahes vektoriseeritud paaris, kus esimene vektor on graafi külgsuhete vektor ilma kaaludeta ja teine vektor sisaldab vastavaid kaalusid (võimalik rakendus C++-s: std::pair). Seega, serva, mis on määratud paariga tippe indeksitega 2i, 2i+1 esimeses vektor, kaal on võrdne elemendiga indeksi i all teises vektor.

Aga miks seda vaja on?

Noh, selle teksti autori jaoks on see mõne ülesande lahendamiseks tundunud piisavalt kasulik. Ametlikult vaadatuna on siin järgmised eelised:

• Külgsuhete vektor, nagu iga teine «loetletav» struktuur, on piisavalt kompaktne, see võtab vähem mälu kui külgtabel (haruldaste graafide puhul) ja on suhteliselt lihtne rakendada.
• Graafi tipud võivad olla põhimõtteliselt ka tähistatud negatiivsete arvudega. Võib-olla on selline «eraklik» vajadus.
• Graafidel võivad olla mitmed servad ja mitmed silmus, millel on erinevad kaalud (positiivsed, negatiivsed ja isegi null). Siin ei ole mingeid piiranguid.
• Lisaks saab servadele määrata erinevaid omadusi – aga sellest räägitakse allpool punktis 4.

Siiski tuleb tunnistada, et see "loendamine" ei eelda kiiret juurdepääsu servadele. Siin tuleb appi külgnevuse assotsiatiivne massiiv, millest räägitakse allpool.

3.2 Külgnevuse assotsiatiivne massiiv

Nii et kui juurdepääs konkreetsele servale, selle kaalule ja teistele omadustele on meile kriitilise tähtsusega, ning mälunõuded ei luba kasutada külgmatrit, siis mõelgem, kuidas saaksime külgjärjendi muuta, et lahendada see ülesanne. Seega on võtmemoment graafi serv, mille saame määrata järjendatud paarina täisarvudest. Millele see sarnaneb? Kas mitte võtmerikkusele assotsiatiivses massiivis? Ja kui nii, siis miks me seda ellu ei viiks? Laske meil luua selline assotsiatiivne massiiv, kus igale võtmele – järjendatud paarile täisarvudest – vastab väärtus – täisarv või reaalnumber, mis määrab serva kaalu. C++ keeles oleks mõistlik rakendada seda struktuuri konteineril std::map (std::map<std::pair, int> või std::map<std::pair, double>), või std::multimap, kui eeldatakse mitmeid servi. Ja nüüd on meil graafide salvestamiseks struktuur, mis kasutab vähem mälu kui "matrix" struktuurid, suudab määrata graafe, millel on mitmeid silmust ja servi ning isegi ei oma ranget nõuet positsioonide numbrite mitte-negatiivsuse osas (ma ei tea, kellele seda vaja on, aga siiski).

Andmete struktuur on nagu "täitke üles", kuid midagi on puudu

Tõepoolest: teatud ülesannete lahendamisel võib meil tekkida vajadus määrata graafide servadele mingid omadused ning vastavalt nende hoidmiseks. Kui need omadused on võimalik üheselt täisarvudeks määrata, on võimalik hoida selliseid "graafe täiendavate omadustega", kasutades laiendatud naabrusvektoreid ja assotsiatiivseid naabrusmassive.

Niisiis, oletame, et meil on kaalumata graaf, mille iga serva jaoks tuleb salvestada näiteks 2 täiendavat tunnust, mis on määratud täisarvudega. Sellisel juhul saab määrata selle naabervektorina järjestatud komplekti, mitte „paaridest”, vaid „kvartettidest” täisarvu (a[2i], a[2i+1], a[2i+2], a[2i+3]…), kus a[2i+2] ja a[2i+3] määravad vastava serva omadused. Kaaludega graafi puhul on järjekord sisuliselt sarnane (erinevuseks on vaid asjaolu, et omadused järgivad serva kaalu ja on määratud elementidega a[2i+3] ja a[2i+4], ning serva ennast määratakse mitte 4, vaid 5 järjestatud numbriga). Kuid graafi, mille servade kaalud ei ole täisarvud, omadused saab kirjutada selle kaalumatutesse komponentidesse.

Raske anatoomsete graafide kasutamisel, mille harude kaalud on täisarvud, on võimalik määrata väärtuseks mitte eraldi number, vaid massiiv (vektor) numbreid, mis määravad, lisaks haru kaalule, kõik muud vajalikud omadused. Probleemiks on see, et mitte täisarvuliste kaalude puhul tuleb omadus määrata ujuva komaga. Jah, see on ebamugav, kuid kui selliseid omadusi pole liiga palju ja kui neid ei määrata liiga „peenelt“ jaotatud numbritena, siis võib see veel töötada. Seega C++-is võivad ulatuslikud anatoomsete graafide massiivid olla määratud järgmiselt: std::map<std::pair, std::vector> või std::map<std::pair, std::vector>, kus „vääna väärtuse vektor” esimene väärtus on haru kaal ja seejärel asuvad selle omaduste numbrilised tähised.

Kübernäide:

Graafide ja algoritmide kohta üldiselt:

1. Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford. Algoritmid: loomine ja analüüs, 2. väljaanne: Tõlge inglise keelest – M.: Williamsi kirjastus, 2011.
2. Harari, Frank. Graafiteooria. M.: Mir, 1973.
Autori ettekande vektorist ja naabrusassotsiatiivsetest massiividest:
3. Chernouhov S.A. Naabrusvektor ja naabruskaardid kui graafide esitamise ja salvestamise viisid / S.A. Chernouhov. Adjacency vector and adjacency map as data structures to represent a graph // Rahvusvahelise teadus-praktilise konverentsi "Innovaatiliste arenduste tulemuste rakendamise probleemid ja nende lahendamise teed" artiklite kogumik (Saratov, 14.09.2019). – Sterlitamak: AMI, 2019, lk 65-69
Kasulikud internetiallikad teemal:
4. prog-cpp.ru/data-graph
5. ejuo.livejournal.com/4518.html

Allikas: habr.com