Tere kõigile.
Selles märkuses otsustasin loetleda peamised andmestruktuurid, mida arvutiteaduses graafikute salvestamiseks kasutatakse, ja räägin veel paarist sellisest struktuurist, mis minu jaoks kuidagi “kristalliseerunud”.
Niisiis, alustame. Aga mitte päris algusest peale – ma arvan, et me kõik teame juba, mis on graaf ja mis see on (suunatud, suunamata, kaalutud, kaalumata, mitme serva ja silmustega või ilma).
Nii et lähme. Milliseid andmestruktuuride valikuid "graafiku salvestamiseks" on meil?
1. Maatriks andmestruktuurid
1.1 Külgnevusmaatriks. Külgnevusmaatriks on maatriks, kus ridade ja veergude pealkirjad vastavad graafiku tippude arvudele ja iga selle elemendi a(i,j) väärtuse määrab tippude vaheliste servade olemasolu või puudumine. i ja j (on selge, et suunamata graafi puhul on selline maatriks sümmeetriline või võime kokku leppida, et salvestame kõik väärtused ainult põhidiagonaali kohal). Kaalumata graafide puhul saab a(i,j) määrata servade arvuga i-st j-ni (kui sellist serva pole, siis a(i,j)= 0) ja kaalutud graafide puhul ka kaalu järgi (kogukaal) nimetatud servadest.
1.2 Esinemismaatriks. Sel juhul on meie graafik salvestatud ka tabelisse, milles reeglina vastavad reanumbrid selle tippude numbritele ja veeru numbrid eelnummerdatud servadele. Kui tipp ja serv langevad teineteisele, siis kirjutatakse vastavasse lahtrisse nullist erinev väärtus (suunamata graafide puhul kirjutatakse 1, kui tipp ja serv on langevad, orienteeritud graafide puhul - "1", kui serv "väljub" tipust ja "-1", kui see "kaasab" (seda on piisavalt lihtne meeles pidada, sest "miinus" märk näib olevat "kaasatud" ka arvus "-1"). Kaalutud graafikute puhul saab jällegi 1 ja -1 asemel määrata serva kogukaalu.
2. Loendamisandmete struktuurid
2.1 Läheduse nimekiri. Noh, siin tundub kõik olevat lihtne. Graafi iga tippu saab üldiselt seostada mis tahes loendusstruktuuriga (loend, vektor, massiiv, ...), mis salvestab kõigi antud tipuga külgnevate tippude numbrid. Suunatud graafide puhul lisame sellisesse loendisse ainult need tipud, millele on objekti tipust "suunatud" serv. Kaalutud graafikute puhul on rakendamine keerulisem.
2.2 Ribide nimekiri. Üsna populaarne andmestruktuur. Servade loend, nagu Captain Obviousness meile ütleb, on tegelikult graafi servade loend, millest igaüks on määratud algustipuga, lõpptipuga (suunamata graafide puhul pole järjekord siin oluline, kuigi ühendamisel saate kasutada erinevaid reegleid, näiteks tippude määramine suurenemise järjekorras) ja kaalu (ainult kaalutud graafikute puhul).
Saate vaadata ülaltoodud maatriksiloendeid üksikasjalikumalt (ja illustratsioonidega), näiteks .
2.3 Külgnevuse massiiv. Mitte kõige levinum struktuur. Oma olemuselt on see külgnemisloendite "pakkimine" ühte loendusstruktuuri (massiivi, vektorit). Sellise massiivi esimesed n (vastavalt graafiku tippude arvule) elementi sisaldavad sama massiivi algusindekseid, millest alates kirjutatakse ritta kõik antud tipuga külgnevad tipud.
Siit leidsin (enda jaoks) kõige arusaadavama seletuse:
3. Külgnevuse vektor ja assotsiatiivne külgnevuse massiiv
Selgus, et nende ridade autor, kes ei olnud professionaalne programmeerija, kuid kes perioodiliselt tegeles graafikutega, tegeles kõige sagedamini servade loenditega. Tõepoolest, on mugav, kui graafikul on mitu silmust ja serva. Ja nii teen klassikaliste servade loendite väljatöötamisel ettepaneku pöörata tähelepanu nende „arengule/harule/modifikatsioonile/mutatsioonile”, nimelt külgnemisvektorile ja assotsiatiivsele naabrusmassiivile.
3.1 Külgnevusvektor
Juhtum (a1): kaalumata graafik
Kaalumata graafi külgnemisvektoriks nimetatakse paarisarvarvude järjestatud hulka (a[2i], a[2i+1],..., kus i on nummerdatud c 0), milles iga numbripaar on a[2i], a[2i+1 ] määrab graafi serva vastavalt tippude a[2i] ja a[2i+1] vahel.
See salvestusvorming ei sisalda teavet selle kohta, kas graafik on suunatud (võimalikud on mõlemad valikud). Digraafivormingu kasutamisel loetakse, et serv on suunatud a[2i]-st punktile a[2i+1]. Siin ja allpool: suunamata graafide puhul saab vajadusel rakendada nõudeid tippude salvestamise järjekorrale (näiteks, et esikohal oleks talle omistatud arvu väiksema väärtusega tipp).
C++ puhul on soovitatav määrata naabrusvektor std::vector abil, sellest ka selle andmestruktuuri nimi.
Juhtum (a2): kaalumata graaf, servade kaalud on täisarvud
Analoogiliselt juhtumiga (a1) nimetame täisarvuliste servakaaludega kaalutud graafiku külgnemisvektorit arvude järjestatud hulgaks (dünaamiliseks massiiviks) (a[3i], a[3i+1], a[3i+2], ..., kus i on nummerdatud c 0), kus iga arvude a[3i], a[3i+1], a[3i+2] “kolmik” määrab graafiku serva nummerdatud a[3i] tippude vahel. ja a[3i+1] vastavalt ning väärtus a [3i+2] on selle serva kaal. Selline graafik võib olla ka suunatud või mitte.
Juhtum (b): kaalumata graaf, mittetäisarvulised servakaalud
Kuna heterogeenseid elemente on võimatu salvestada näiteks ühte massiivi (vektorisse), on võimalik järgmine teostus. Graafik salvestatakse vektoripaari, milles esimene vektor on graafi naabrusvektor ilma kaalusid määramata ja teine vektor sisaldab vastavaid kaalusid (võimalik teostus C++ jaoks: std::pair ). Seega on esimese vektori indeksite 2i, 2i+1 all olevate tippude paariga määratletud serva kaal võrdne teise vektori indeksi i all oleva elemendiga.
No miks see vajalik on?
Noh, nende ridade autor leidis, et see on paljude probleemide lahendamisel üsna kasulik. Noh, formaalsest vaatenurgast on sellel järgmised eelised:
- Külgnevusvektor, nagu iga teine “loendav” struktuur, on üsna kompaktne, võtab vähem mälu kui naabrusmaatriks (hõredate graafikute jaoks) ja seda on suhteliselt lihtne rakendada.
- Graafi tippe saab põhimõtteliselt tähistada ka negatiivsete arvudega. Mis siis, kui sellist "perverssust" on vaja?
- Graafikud võivad sisaldada mitut serva ja mitut tsüklit erineva kaaluga (positiivne, negatiivne, isegi null). Siin pole piiranguid.
- Samuti saab servadele määrata erinevaid omadusi – aga selle kohta vaata täpsemalt 4. osast.
Siiski tuleb tunnistada, et see "nimekiri" ei tähenda kiiret juurdepääsu servale. Ja siin tuleb appi Associative Adjacency Array, mida arutatakse allpool.
3.2 Assotsiatiivne külgnevuse massiiv
Seega, kui juurdepääs konkreetsele servale, selle kaalule ja muudele omadustele on meie jaoks kriitilise tähtsusega ning mälunõuded ei võimalda meil kasutada naabrusmaatriksit, siis mõelgem, kuidas saaksime selle probleemi lahendamiseks külgnemisvektorit muuta. Seega on võtmeks graafiku serv, mida saab määrata järjestatud täisarvude paarina. Kuidas see välja näeb? Kas see pole assotsiatiivse massiivi võti? Ja kui jah, siis miks me seda ei rakenda? Olgu meil assotsiatiivne massiiv, kus iga võti – järjestatud täisarvude paar – on seotud väärtusega – täisarv või reaalarv, mis määrab serva kaalu. C++ puhul on soovitatav seda struktuuri rakendada std::map konteineri (std::map) põhjal , int> või std::map , double>) või std::multimap, kui eeldatakse mitut serva. Noh, meil on graafide salvestamise struktuur, mis võtab vähem mälu kui maatriksstruktuurid, suudab defineerida mitme silmuse ja servaga graafikuid ning millel pole isegi rangeid nõudeid tipuarvude mittenegatiivsusele (ma ei tea kes seda vajab, aga siiski).
4. Andmestruktuurid on täis, kuid midagi on puudu
Ja see on tõsi: paljude probleemide lahendamisel peame võib-olla määrama graafiku servadele mõned omadused ja need vastavalt salvestama. Kui neid tunnuseid on võimalik üheselt taandada täisarvudeks, siis on võimalik selliseid “lisatunnustega graafikuid” salvestada, kasutades külgnemisvektori ja assotsiatiivse naabrusmassiivi laiendatud versioone.
Seega olgu meil kaalumata graaf, mille iga serva jaoks on vaja salvestada näiteks 2 täisarvudega määratud lisatunnust. Sel juhul on võimalik selle naabrusvektorit määratleda mitte "paaride", vaid täisarvude "kvartettide" järjestatud hulgana (a[2i], a[2i+1], a[2i+2], a [2i+3]…) , kus a[2i+2] ja a[2i+3] määravad vastava serva omadused. Täisarvuliste servade kaaluga graafiku puhul on järjekord üldiselt sarnane (ainus erinevus seisneb selles, et atribuudid järgivad serva kaalu ja neid täpsustavad elemendid a[2i+3] ja a[2i+4] , ja serv ise määratakse mitte 4, vaid 5 järjestatud numbriga). Ja mittetäisarvuliste servakaaludega graafiku puhul saab omadused kirjutada selle kaalumata komponenti.
Täisarvulise serva kaaluga graafide assotsiatiivse naabrusmassiivi kasutamisel saab väärtusena määrata mitte ühe arvu, vaid arvude massiivi (vektori), mis määrab lisaks serva kaalule ka kõik muud vajalikud. Funktsioonid. Samal ajal tekitab mittetäisarvude puhul ebamugavust vajadus määrata ujukomanumbriga märk (jah, see on ebamugavus, kuid kui selliseid märke pole nii palju ja kui te seda ei tee Ärge määrake neid liiga "keerukaks" kahekordseks, siis ei pruugi see olla midagi) . See tähendab, et C++-s saab laiendatud assotsiatiivseid naabrusmassiive defineerida järgmiselt: std::map , std::vector> või std::map , std::vector, milles "võtmeväärtuse vektori" esimene väärtus on serva kaal ja seejärel asuvad selle karakteristikute numbrilised tähised.
Kirjandus:
Graafikute ja algoritmide kohta üldiselt:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algoritmid: ehitus ja analüüs, 2. trükk: Trans. inglise keelest – M.: Williamsi kirjastus, 2011.
2. Harari Frank. Graafiteooria. M.: Mir, 1973.
Autori aruanne nende samade vektorite ja külgnemiste assotsiatiivse massiivi kohta:
3. Tšernoukhov S.A. Külgnevusvektor ja assotsiatiivne naabruse massiiv kui viisid graafikute esitamiseks ja salvestamiseks / SA Tšernouhov. Adjacency vector and adcency map andmestructures to represent a graph // Rahvusvahelise teadus-praktilise konverentsi „Innovaatiliste arenduste tulemuste rakendamise probleemid ja nende lahendamise viisid“ artiklite kogumik (Saratov, 14.09.2019. september 2019). – Sterlitamak: AMI, 65, lk. 69-XNUMX
Kasulikud veebiallikad selle teema kohta:
4.
5.
Allikas: www.habr.com