Andmete struktuurid graafide säilitamiseks: ülevaade olemasolevatest ja kaks "peaaegu uut"

Tere kõigile.

Selles märkmes otsustasin loetleda peamised andmestruktuurid, mida kasutatakse graafide hoidmiseks infotehnoloogias, ja rääkida ka paarist sellisest struktuurist, mis mul ühel hetkel "kristalliseerusid".

Nii et alustame. Kuid mitte algusest - ma arvan, et me kõik teame, mis on graaf ja millised need võivad olla (suunatud, suunamata, kaalutud, kaalutud, mitme servaga ja silmadega või ilma),

Nii et edasi. Milliseid andmestruktuuride valikuid „graafide säilitamiseks” meil on.

1. Matriitsistruktuurid

1.1 Siduva matriits. Siduva matriits on matriit, kus ridade ja veergude pealkirjad vastavad graafi sõlmede numbritele ning iga elemendi väärtus a(i,j) määratakse sõlmede i ja j vahelise serva olemasolu või puudumise järgi (selgelt, et suunamata graafi selline matriit on sümmeetriline, või saame kokku leppida, et kõik väärtused salvestame ainult peadiagonaali kohal). Kaalumata graafide puhul saab a(i,j) määrata servade arvu i-st j-ni (kui sellist servi pole, siis a(i,j)= 0), kaalutud graafide puhul samuti - serva massiga (kokkuvõtlik kaal).

1.2 Incidendi matriits. Sellisel juhul salvestatakse meie graaf samuti tabelisse, kus reede numbrid vastavad tavaliselt tema sõlmedele ja veeru numbrid eelnevalt nummerdatud servadele. Kui sõlm ja serv on omavahel seotud, siis vastavasse lahtrisse kirjutatakse mitte null väärtus (suunamata graafide puhul kirjutatakse 1, kui sõlm ja serv on seotud, suunatud graafide puhul - "1", kui serv "väljub" sõlmest ja "-1", kui see "siseneb" (kergesti meeldejääv, kuna märk „miinus“ siseneb ka numbrite "-1" hulka)). Kaalutud graafide puhul saab taas 1 ja -1 asemel märkida serva kogumassi.

2. Loendid andmestruktuurid

2.1 Külgne loend. Siin on kõik üsna lihtne. Iga graafi tippu saab üldiselt vastandada mis tahes loetelustruktuur (loend, vektor, massiiv, ...), kus hoitakse iga tippu, mis on antud tippu naabrid. Suunatud graafide puhul lisame sellesse loendisse vaid need tipud, kuhu on "suunatud" serv tipust-näitajast. Kaalutud graafide puhul on rakendamine keerulisem.

2.2 Servade loend. Üsna populaarne andmestruktuur. Servade loend, nagu meile ütleb Kapten Ilmselgus, esindab tegelikult graafi servade loendit, millest igaüks on määratud algtippu, lõpptippu (suunamata graafide puhul pole siin järjekorra olemasolu oluline, kuigi ühtsuse huvides võib kasutada erinevaid reegleid, näiteks määrata tipud kasvavas järjekorras) ja kaalu (ainult kaalutud graafide puhul).

Kasutatud loendi-matriitside kohta võib lähemalt (ja illustratsioonidega) lugeda, näiteks siit.

2.3 Naabruse massiiv. Ei ole kõige sagedamini esinev struktuur. Sisult esindab see loendusehnvuse massiivi «pakendamist» ühte loetelustruktuuri (massiiv, vektor). Esimesed n (graafi tippude arvu järgi) elementi sellises massiivis sisaldavad antud massiivi algindeksid, alates millest on selles järjestikku kirjas kõik naabrina olevad tipud.

Siit leidsin kõige arusaadavam (enda jaoks) selgitus: ejuo.livejournal.com/4518.html

3. Naabruse vektor ja Assotsiatiivne naabruse massiiv

Nii juhtus, et nende ridade autor, olles professionaalne programmijatega, kuid erilisel juhul olnud graafidega, on tihti pidanud tegelema servade loenditega. Tõepoolest, on mugav, kui graafis on mitu silmust ja serva. Ja nii, arendades klassikalisi servade loendeid, pakun välja tähelepanu pöörata nende "arendamisele / harutamisele / modifitseerimisele / mutatsioonile", nimelt: naabruse vektorile ja assotsiatiivsele naabruse massiivile.

3.1 Naabruse vektor

Juhtum (a1): kaalutum graaf

Nimelt nimetame kaalumatuks graafiks naabruse vektoriks paarisarvuliste täisarvude järjestatud kogumit (a[2i], a[2i+1],…, kus i nummerdatakse 0-st), kus iga numbri paar a[2i], a[2i+1] määrab graafi serva tipude vahel a[2i] ja a[2i+1] vastavalt.
See record format does not contain information on whether the graph is directed (both options are possible). When using the format for an org graph, it is assumed that the edge is directed from a[2i] to a[2i+1]. Hereinafter: for undirected graphs, if necessary, the requirements for the order of writing vertices can be applied (for example, to have the vertex with the smaller assigned number go first).

In C++, it is advisable to define the adjacency vector using std::vector, hence the name of this data structure.

Case (a2): unweighted graph, edge weights are integers

By analogy with case (a1), we will call the adjacency vector for a weighted graph with integer edge weights an ordered set (dynamic array) of numbers (a[3i], a[3i+1], a[3i+2],…, where i is numbered from 0), where each 'triplet' of numbers a[3i], a[3i+1], a[3i+2] defines an edge of the graph between the vertices numbered a[3i] and a[3i+1] respectively, and the value a[3i+2] is the weight of this edge. Such a graph can also be directed or undirected.

Case (b): unweighted graph, edge weights are non-integer

Given that a single array (vector) cannot store heterogeneous elements, for example, the following implementation is possible. The graph is stored in a pair of vectors, where the first vector is the adjacency vector of the graph without specifying weights, and the second vector contains the corresponding weights (possible implementation for C++: std::pair). Thus, for an edge defined by a pair of vertices at indices 2i, 2i+1 of the first vector, the weight will be equal to the element at index i of the second vector.

But why is this necessary?

Well, to the author of these lines, it seemed quite useful for solving a number of problems. From a formal point of view, there will be such advantages:

• The adjacency vector, like any other 'enumerative' structure, is quite compact, occupies less memory than the adjacency matrix (for sparse graphs), and is relatively easy to implement.
• The vertices of the graph can, in principle, be labeled with negative numbers. After all, such 'twisting' may be needed.
• Graphs can contain multiple edges and multiple loops, with different weights (positive, negative, or even zero). There are no restrictions here.
• Samuti saab harudele määrata erinevaid omadusi – kuid selle kohta vt p. 4.

Siiski tuleb tunnistada, et see „nimekiri” ei tähenda kiiret juurdepääsu harule. Ja siin tõttab meile appi Assotsiatiivne külgne massiiv, millest räägime allpool.

3.2 Assotsiatiivne külgne massiiv

Seega, kui juurdepääs konkreetsele harule, selle kaalule ja muudele omadustele on meie jaoks kriitilise tähtsusega, kuid mälunõuded ei luba kasutada külgnevad maatriksit, siis mõelgem, kuidas saaksime külgnuektorist muuta, et seda ülesannet lahendada. Seega on võtmeküsimuseks graafi haru, mille saab esitada järjestatud paarina täisarve. Mida see meenutab? Kas see pole nagu võtme assotsiatiivses massiivis? Ja kui nii, siis miks mitte seda ellu viia? Olgu meil selline assotsiatiivne massiiv, kus igale võtmele – järjestatud paar täisarve – vastab väärtus – täisarv või reaalnumber, mis määrab haru kaalu. C++-s on mõistlik seda struktuuri rakendada konteineri std::map (std::map <std::pair , int> või std::map <std::pair , double>), või std::multimap, kui eeldatakse mitmeid harusid. Noh, ja meil on struktuur graafide säilitamiseks, mis kasutab vähem mälu kui „maatrikstruktuurid”, suudab määrata graafe mitmete silmade ja harudega ning ei oma isegi ranged nõuded tippude mitte-negatiivsusele (ma ei tea, kellele see vajalik on, kuid siiski).

4. Andmestruktuurid on kui „valmistada”, kuid midagi on puudu

Ja tõepoolest: mitmete ülesannete lahendamisel võib meil tekkida vajadus määrata graafi harudele mingid omadused ja seega need säilitada. Kui need omadused saab üheselt täisarvudeks vähendada, siis on võimalik säilitada selliseid „lisamärkidega graafikuid”, kasutades laiendatud versioone külgneva vektori ja assotsiatiivse massiivi põhjal.

Nii et, olgu meil kaalumata graaf, mille iga serva kohta on vajalik salvestada näiteks 2 täiendavat omadust, mis on määratud täisarvudega. Sellisel juhul on võimalik määrata selle külgvektor järjestatud kogumina mitte "paaridest", vaid "nelikutest" täisarve (a[2i], a[2i+1], a[2i+2], a[2i+3]...), kus a[2i+2] ja a[2i+3] määravad vastava servi omadused. Kaalutud servadega graafi puhul on järjekord üldiselt sarnane (erinevus on vaid selles, et omadused järgivad serva kaalu ja on määratud elementidega a[2i+3] ja a[2i+4], ning ise serv on määratud mitte 4, vaid 5 järjestatud numbriga). Niisiis, graafi puhul, mille servade kaalud ei ole täisarvud, saab omadused talletada selle kaalumatutes komponentides.

Kasutades külgseose assotsiatiivset massi, on võimalik kaalutud servadega graafide puhul määrata väärtusena mitte eraldi number, vaid massiiv (vektor) numbreid, mis määravad, peale serva kaalu, kõik tema muud vajalikud omadused. Selle juurde käiv ebamugavus, kui kaalud ei ole täisarvud, on vajadus määrata omadus ujuva koma numbriga (jah, see on ebameeldivus, kuid kui selliseid omadusi ei ole liiga palju ja kui mitte määrata neid liiga „nutikate“ double'itega, siis võib-olla pole see ka halb). Nii et C++-is võivad laiendatud assotsiatiivsed massi külgseosed olla määratud järgmised: std::map <std::pair , std::vector> või std::map <std::pair , std::vector>, kusjuures esimene väärtus "vektor- väärtus-võtme järgi" on serva kaal ja seejärel asetsevad tema omaduste numbrilised tähised.

Käesolev kirjandus:

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 – Moskva: Williamsi kirjastus, 2011.
2. Harari, Frank. Graafide teooria. Moskva: Mir, 1973.
Autori ettekande kohta nende vektori ja assotsiatiivse massi külgseose kohta:
3. Черноухов С.А. Külleu väärtus ja seosekaart kui andmestruktuurid graafide esitamiseks ja salvestamiseks // S.A. Chernouhov. Seoste vektor ja seosekaart andmestruktuuridena graafi esitlemiseks // Rahvusvahelise teadus- ja praktikaseminaride kogumik teemal "Uuenduslike arenduste tulemuste rakendamise probleemid ja nende lahendamise teed" (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