Ahojte všetci.
V tejto poznámke som sa rozhodol uviesť hlavné dátové štruktúry používané na uchovávanie grafov v informatike a tiež sa podelím o niekoľko ďalších štruktúr, ktoré sa mi akosi "vykristalizovali".
Tak začnime. Ale nie od začiatku – myslím, že vieme, čo je graf a aké sú typy (orientované, neorientované, vážené, nevážené, s viacerými hranami a slučkami alebo bez nich).
Tak poďme na to. Aké možnosti dátových štruktúr pre "grafové uchovávanie" máme.
1. Matricové dátové štruktúry
1.1 Matica súvislosti. Matica súvislosti je maticou, kde hlavičky riadkov a stĺpcov zodpovedajú číslam vrcholov grafu, pričom hodnota každého jej prvku a(i,j) je definovaná prítomnosťou alebo neprítomnosťou hrán medzi vrcholmi i a j (je jasné, že pre neorientovaný graf bude táto matica symetrická, alebo sa môžeme dohodnúť, že všetky hodnoty uchovávame len nad hlavnou diagonálou). Pre nevážené grafy môžeme a(i,j) určiť počtom hrán z i do j (ak taká hrana neexistuje, tak a(i,j)= 0), a pre vážené tiež – váhou (súhrnnou váhou) spomenutých hrán.
1.2 Matica incidencie. V tomto prípade je náš graf tiež uložený v tabuľke, v ktorej sú zvyčajne číslam riadkov priradené čísla jeho vrcholov a číslam stĺpcov – predtým očíslované hrany. Ak sú vrchol a hrana incidentné, tak sa v príslušnej bunke zapíše nenulová hodnota (pre neorientované grafy sa zapisuje 1 v prípade incidentnosti vrcholu a hrany, pre orientované – "1", ak hrana "vychádza" z vrcholu a "-1", ak do neho "vstupuje" (pamätať si to je celkom jednoduché, pretože znamienko "mínus" tiež akoby "vstupuje" do čísla "-1"). Pre vážené grafy opäť namiesto 1 a -1 môžeme uvádzať súhrnnú váhu hrany.
2. Vypisovacie dátové štruktúry
2.1 Zoznam susednosti. Tu to vyzerá celkom jednoducho. Každej vrcholu grafu je možné v zásade priradiť akúkoľvek enumeratívnu štruktúru (zoznam, vektor, pole, …), v ktorej sa budú uchovávať čísla všetkých vrcholov pripojených k danej. Pre orientované grafy budeme do takého zoznamu zapisovať len tie vrcholy, do ktorých vedie „orientovaná“ hrana z vrcholu-priznaku. Pre vážené grafy bude implementácia o niečo zložitejšia.
2.2 Zoznam hrán. Celkom populárna štruktúra údajov. Zoznam hrán, ako nám naznačuje Kapitán Očividnosť, a predstavuje vlastne zoznam hrán grafu, pričom každá z nich je určená počiatočným vrcholom, konečným vrcholom (pre neorientované grafy nie je poradie významné, hoci pre jednotnosť je možné použiť rôzne pravidlá, napríklad uvádzať vrcholy v poradí vzostupu) a váhou (len pre vážené grafy).
O vyššie uvedených zoznamoch-matričkách si môžete pozrieť podrobnejšie (a s ilustráciami), napríklad .
2.3 Pole susednosti. Nie je to najčastejšie sa vyskytujúca štruktúra. V podstate predstavuje formu „balenia“ zoznamov susednosti do jednej enumeratívnej štruktúry (pole, vektor). Prvé n (podľa počtu vrcholov grafu) prvkov takého poľa obsahujú štartovacie indexy rovnakého poľa, od ktorých sú v ňom postupne zapísané všetky vrcholy pripojené k danej.
Tu som našiel najjasnejšie (pre seba) vysvetlenie:
3. Vektor susednosti a Asociatívny pole susednosti
Stalo sa tak, že autor týchto riadkov, ktorý nie je profesionálnym programátorom, ale mal občas dočinenia s grafmi, sa najčastejšie stretával so zoznamami hrán. Naozaj, je pohodlné, ak v grafe existujú viaceré slučky a hrany. A tak, v rozvoji klasických zoznamov hrán, navrhujem venovať pozornosť aj ich „rozvoju/odvetveniu/modifikácii/mutácii“, konkrétne: vektoru susednosti a asociatívnemu poľu susednosti.
3.1 Vektor susednosti
Prípad (a1): nevážený graf
Budeme nazývať vektorom susednosti pre nevážený graf usporiadanú množinu párneho počtu celých čísel (a[2i], a[2i+1],…, kde i je očíslované od 0), v ktorej každá dvojica čísel a[2i], a[2i+1] definuje hranu grafu medzi vrcholmi a[2i] a a[2i+1] príslušne.
Tento formát zápisu neobsahuje informácie o tom, či je graf orientovaný (obidva varianty sú možné). Pri použití formátu pre orientovaný graf sa predpokladá, že hrana je nasmerovaná z a[2i] na a[2i+1]. Tu a ďalej: pre neorientované grafy sa, ak je to potrebné, môžu uplatniť požiadavky na poradie zápisu vrcholov (napríklad aby prvý bol vrchol s menšou hodnotou priradeného čísla).
V C++ je rozumné definovať zoznam susedov pomocou std::vector, odtiaľ bolo vybrané názov tejto dátovej štruktúry.
Prípad (a2): neohodnotený graf, váhy hrán sú celé čísla.
Podobne ako v prípade (a1) nazveme zoznamom susedov pre ohodnotený graf s celočíselnými váhami hrán usporiadanú množinu (dynamické pole) čísel (a[3i], a[3i+1], a[3i+2],…, kde i začína od 0), kde každý 'triplet' čísel a[3i], a[3i+1], a[3i+2] určuje hranu grafu medzi vrcholmi s číslami a[3i] a a[3i+1] a hodnota a[3i+2] je váha tejto hrany. Takýto graf môže byť tiež orientovaný alebo nie.
Prípad (b): neohodnotený graf, váhy hrán nie sú celé čísla.
Keďže v jednom poli (zozname) nie je možné uchovávať heterogénne prvky, je možná nasledovná implementácia. Graf je uložený v páre zoznamov, kde prvý zoznam je zoznamom susedov grafu bez uvádzania váh, a druhý zoznam obsahuje príslušné váhy (možná implementácia pre C++: std::pair). Týmto spôsobom pre hranu definovanú párom vrcholov na indexoch 2i, 2i+1 prvého zoznamu bude váha rovná prvku na indexe i druhého zoznamu.
Ale na čo to potrebujeme?
Pre autora týchto riadkov sa to zdalo dostatočne užitočné pre riešenie niekoľkých úloh. A formálne povedané, tu budú také výhody:
- Zoznam susedov, ako každá iná 'enumeratívna' štruktúra, je dostatočne kompaktný, zaberá menej pamäte ako matica susednosti (pre riedke grafy), relatívne jednoducho sa implementuje.
- Vrcholom grafu môžu byť v zásade priradené aj záporné čísla. Možno to tiež bude potrebné a takýto 'úlet'.
- Grafy môžu obsahovať viacnásobné hrany a viacnásobné slučky, a to aj s rôznymi váhami (klasicky kladné, záporné, dokonca nulové). Žiadne obmedzenia tu nie sú.
- A ešte je možné priradiť rôzne vlastnosti k hranám – ale o tom pozri bod 4.
Avšak treba uznať, že táto „zoznamová“ štruktúra nepodporuje rýchly prístup k hrane. A sem prichádza na pomoc asociačný zoznam susednosti, o čom – nižšie.
3.2 Asociačný zoznam susednosti
Takže, ak je pre nás kritický prístup ku konkrétnej hrane, jej váhe a iným vlastnostiam, a požiadavky na pamäť neumožňujú použiť maticu susednosti, poďme premýšľať, ako môžeme zmeniť zoznam susednosti, aby sme vyriešili tento problém. Kľúčom je hrana grafu, ktorú môžeme definovať ako usporiadanú dvojicu celých čísel. Na čo to však pripomína? Nie je to kľúč v asociačnom zozname? Ak áno, prečo by sme to nemohli implementovať? Nech máme taký asociačný zoznam, kde každej dvojici celých čísel bude priradená hodnota – celé alebo reálne číslo, ktoré určuje váhu hrany. V C++ je rozumné realizovať túto štruktúru na základe kontajnera std::map (std::map <std::pair , int> alebo std::map <std::pair , double>), alebo std::multimap, ak sa predpokladajú viaceré hrany. A tak, máme štruktúru na ukladanie grafov, ktorá zaberá menej pamäte ako „matricové“ štruktúry, môže definovať grafy s viacerými slučkami a hranami a dokonca nemá prísne požiadavky na nezáporné čísla vrcholov (neviem, komu to je potrebné, ale predsa).
4. Štruktúry dát, aj keby si ich naplnil, stále niečo chýba
Naozaj: pri riešení niektorých úloh môžeme čeliť potrebe priradiť hranám grafu nejaké znaky a zodpovedajúco ich uložiť. Ak je možné jednoznačne zredukovať tieto znaky na celé čísla, je možné ukladať takéto „grafy s dodatočnými znakmi“ využitím rozšírených verzií zoznamu susednosti a asociačného zoznamu susednosti.
Tak nech máme nevážny graf, pre každý jeho okraj, ktorý potrebuje uchovávať napríklad 2 ďalšie znaky, zadané celými číslami. V tomto prípade je možné určiť jeho susedný vektor ako usporiadanú sadu nie "párov", ale "štvoríc" celých čísel (a[2i], a[2i+1], a[2i+2], a[2i+3]…), kde a[2i+2] a a[2i+3] určia znaky príslušného okraja. Pre graf s celými hmotnosťami okrajov je poradie v zásade rovnaké (rozdielom bude len to, že znaky budú nasledovať po hmotnosti okraja a budú zadané prvkami a[2i+3] a a[2i+4], pričom okraj bude zadaný nie 4, ale 5 usporiadanými číslami). A pre graf s necelými hmotnosťami okrajov budú znaky možné zaznamenať v jeho nevážnej komponente.
Pri používaní asociatívneho poľa susednosti pre grafy s celými hmotnosťami okrajov je možné ako hodnotu zadať nie jedno číslo, ale pole (vektor) čísel, ktoré určujú, okrem hmotnosti okraja, všetky jeho ďalšie potrebné znaky. Pričom nevýhodou pre prípad necelých hmotností bude nutnosť zadania znaku číslom s plávajúcou desatinnou čiarkou (áno, to je nevýhoda, ale ak takých znakov nie je veľa a ak sa nezadávajú príliš "chytré" double, tak to, možno, nie je nič). A teda v C++ môžu byť rozšírené asociatívne polia susednosti zadané nasledovne: std::map <std::pair , std::vector> alebo std::map <std::pair , std::vector, pričom prvou hodnotou v "vektore-hodnote-po-kľúči" bude hmotnosť okraja, a ďalej sa nachádzajú číselné označenia jeho znakov.
Literatúra:
O grafoch a algoritmoch vôbec:
1. Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford. Algoritmy: konštrukcia a analýza, 2. vydanie: Pre. z angličtiny – M.: Vydavateľský dom "Williams", 2011.
2. Harari, Frank. Teória grafov. M.: Mir, 1973.
Prezentácia autora o týchto vektoroch a asociatívnych poliach susednosti:
3. Černoukh S.A. Vektor susednosti a asociatívna mapa susednosti ako spôsoby reprezentácie a ukladania grafov / S.A. Černoukh. Vektor susednosti a asociatívna mapa ako dátové štruktúry na reprezentáciu grafu // Zborník príspevkov Medzinárodnej vedecko-praktickej konferencie „Problémy implementácie výsledkov inovačných vypracovaní a cesty ich riešenia“ (Saratov, 14.09.2019). – Sterlitamak: AMI, 2019, s. 65-69
Užitočné internetové zdroje k téme:
4.
5.
Zdroj: habr.com
