Ahoj všetci
V tejto poznámke som sa rozhodol uviesť hlavné dátové štruktúry používané na ukladanie grafov v informatike a tiež poviem o niekoľkých ďalších štruktúrach, ktoré sa mi nejako „vykryštalizovali“.
Takže, začnime. Ale nie od úplného začiatku - myslím, že už všetci vieme, čo je graf a čo je to (riadený, neorientovaný, vážený, nevážený, s alebo bez viacerých hrán a slučiek).
Tak, poďme. Aké možnosti dátových štruktúr na „ukladanie grafov“ máme?
1. Maticové dátové štruktúry
1.1 Matica susedstva. Matica susedstva je matica, kde nadpisy riadkov a stĺpcov zodpovedajú číslam vrcholov grafu a hodnota každého z jej prvkov a(i,j) je určená prítomnosťou alebo absenciou hrán medzi vrcholmi. i a j (je jasné, že pre neorientovaný graf bude takáto matica symetrická, prípadne sa dohodneme, že všetky hodnoty uložíme len nad hlavnú uhlopriečku). Pre nevážené grafy možno a(i,j) nastaviť počtom hrán od i do j (ak taká hrana nie je, potom a(i,j)= 0) a pre vážené grafy aj váhou (celková hmotnosť) spomínaných hrán.
1.2 Matica incidencie. V tomto prípade je náš graf uložený aj v tabuľke, v ktorej spravidla čísla riadkov zodpovedajú číslam jeho vrcholov a čísla stĺpcov zodpovedajú vopred očíslovaným hranám. Ak sú vrchol a hrana navzájom incidentné, potom sa do príslušnej bunky zapíše nenulová hodnota (pre neorientované grafy sa zapíše 1, ak sú vrchol a hrana incidentné, pre orientované grafy - „1“, ak hrana „vystúpi“ z vrcholu a „-1“, ak doň „zahŕňa“ (je dosť ľahké si to zapamätať, pretože sa zdá, že znamienko „mínus“ je „zahrnuté“ aj v čísle „-1“)). Pre vážené grafy opäť namiesto 1 a -1 môžete určiť celkovú hmotnosť hrany.
2. Enumeračné dátové štruktúry
2.1 Zoznam susedstva. Zdá sa, že tu je všetko jednoduché. Každý vrchol grafu môže byť vo všeobecnosti spojený s ľubovoľnou enumeračnou štruktúrou (zoznam, vektor, pole, ...), v ktorej budú uložené čísla všetkých vrcholov susediacich s daným. Pre orientované grafy doplníme do takéhoto zoznamu len tie vrcholy, ku ktorým existuje „nasmerovaná“ hrana z vrcholu prvku. V prípade vážených grafov bude implementácia zložitejšia.
2.2 Zoznam rebier. Pomerne populárna dátová štruktúra. Zoznam hrán, ako nám hovorí Captain Obviousness, je vlastne zoznam hrán grafu, z ktorých každá je špecifikovaná počiatočným vrcholom, koncovým vrcholom (pre neorientované grafy tu poradie nie je dôležité, aj keď pre zjednotenie môžete použiť rôzne pravidlá, napríklad špecifikovať vrcholy v poradí zvyšovania) a váhu (len pre vážené grafy).
Vyššie uvedené maticové zoznamy si môžete pozrieť podrobnejšie (a s ilustráciami), napr. .
2.3 Pole susedstva. Nie najbežnejšia štruktúra. Vo svojom jadre je to forma „zbalenia“ susedných zoznamov do jednej enumeračnej štruktúry (pole, vektora). Prvých n (podľa počtu vrcholov grafu) prvkov takéhoto poľa obsahuje počiatočné indexy toho istého poľa, od ktorého sa zapisujú všetky vrcholy susediace s daným v riadku.
Tu som našiel najzrozumiteľnejšie (pre seba) vysvetlenie:
3. Vektor susedstva a pole pridruženého susedstva
Ukázalo sa, že autor týchto riadkov, ktorý nie je profesionálnym programátorom, ale pravidelne sa zaoberal grafmi, sa najčastejšie zaoberal zoznamami hrán. V skutočnosti je vhodné, ak má graf viacero slučiek a hrán. A tak pri vývoji klasických zoznamov hrán navrhujem venovať pozornosť ich „vývoju/vetveniu/modifikácii/mutácii“, a to: vektoru susednosti a asociatívnemu poli susednosti.
3.1 Vektor susedstva
Prípad (a1): nevážený graf
Vektor susednosti pre nevážený graf budeme nazývať usporiadanou množinou párneho počtu celých čísel (a[2i], a[2i+1],..., kde i je očíslované c 0), v ktorej každá dvojica čísel je a[2i], a[2i+1 ] určuje hranu grafu medzi vrcholmi a[2i] a a[2i+1].
Tento formát záznamu neobsahuje informácie o tom, či je graf orientovaný (možné sú obe možnosti). Pri použití formátu digrafu sa predpokladá, že hrana smeruje z a[2i] do a[2i+1]. Tu a nižšie: pre neorientované grafy možno v prípade potreby uplatniť požiadavky na poradie zaznamenávania vrcholov (napríklad, aby bol na prvom mieste vrchol s nižšou hodnotou čísla, ktoré je mu priradené).
V C++ je vhodné špecifikovať vektor susedstva pomocou std::vector, odtiaľ názov tejto dátovej štruktúry.
Prípad (a2): nevážený graf, váhy hrán sú celé čísla
Analogicky s prípadom (a1) nazývame vektor susednosti pre vážený 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 je očíslované c 0), kde každá „trojica“ čísel a[3i], a[3i+1], a[3i+2] určuje hranu grafu medzi vrcholmi očíslovanými a[3i] a a[3i+1] a hodnota a [3i+2] je váha tejto hrany. Takýto graf môže byť tiež smerovaný alebo nie.
Prípad (b): nevážený graf, neceločíselné váhy hrán
Pretože nie je možné uložiť heterogénne prvky do jedného poľa (vektora), je možná nasledujúca implementácia. Graf je uložený v páre vektorov, v ktorých prvý vektor je vektor susednosti grafu bez určenia váh a druhý vektor obsahuje zodpovedajúce váhy (možná implementácia pre C++: std::pair ). Teda pre hranu definovanú dvojicou vrcholov pod indexmi 2i, 2i+1 prvého vektora bude váha rovná prvku pod indexom i druhého vektora.
Prečo je to potrebné?
Autorom týchto riadkov sa to celkom hodilo na riešenie množstva problémov. Z formálneho hľadiska to budú tieto výhody:
- Vektor susednosti, ako každá iná „enumeratívna“ štruktúra, je pomerne kompaktný, zaberá menej pamäte ako matica susednosti (pre riedke grafy) a je relatívne ľahko implementovateľný.
- Vrcholy grafu môžu byť v zásade označené aj zápornými číslami. Čo ak je takáto „zvrátenosť“ potrebná?
- Grafy môžu obsahovať viacero hrán a viacero slučiek s rôznou váhou (kladná, záporná, dokonca nulová). Neplatia tu žiadne obmedzenia.
- Hranám môžete tiež priradiť rôzne vlastnosti – ale viac o tom nájdete v časti 4.
Treba však priznať, že tento „zoznam“ neznamená rýchly prístup k okraju. A tu prichádza na pomoc Associative Adjacency Array, o ktorom sa hovorí nižšie.
3.2 Pole asociatívnej susednosti
Ak je teda pre nás prístup ku konkrétnej hrane, jej váhe a iným vlastnostiam kritický a pamäťové požiadavky nám neumožňujú použiť maticu susednosti, potom sa zamyslime nad tým, ako môžeme zmeniť vektor susednosti, aby sme tento problém vyriešili. Kľúčom je teda hrana grafu, ktorá môže byť špecifikovaná ako usporiadaný pár celých čísel. Ako to vyzerá? Nie je to kľúč v asociatívnom poli? A ak áno, prečo to neimplementujeme? Majme asociatívne pole, kde každý kľúč - usporiadaný pár celých čísel - bude spojený s hodnotou - celým číslom alebo reálnym číslom, ktoré udáva váhu hrany. V C++ je vhodné implementovať túto štruktúru založenú na kontajneri std::map (std::map , int> alebo std::map , double>), alebo std::multimap, ak sa očakávajú viaceré hrany. Nuž, máme štruktúru na ukladanie grafov, ktorá zaberá menej pamäte ako „maticové“ štruktúry, dokáže definovať grafy s viacerými slučkami a hranami a nemá ani prísne požiadavky na nezápornosť čísel vrcholov (neviem kto to potrebuje, ale predsa).
4. Dátové štruktúry sú plné, ale niečo chýba
A je to pravda: pri riešení množstva problémov možno budeme musieť okrajom grafu priradiť niektoré charakteristiky a podľa toho ich uložiť. Ak je možné tieto vlastnosti jednoznačne zredukovať na celé čísla, potom je možné takéto „grafy s ďalšími vlastnosťami“ uložiť pomocou rozšírených verzií vektora susednosti a asociatívneho poľa susedstva.
Majme teda nevážený graf, pre každú hranu ktorého je potrebné uložiť napríklad 2 ďalšie vlastnosti špecifikované celými číslami. V tomto prípade je možné definovať jeho vektor susednosti ako usporiadanú množinu nie „párov“, ale „kvartetov“ celých čísel (a[2i], a[2i+1], a[2i+2], a [2i+3]…) , kde a[2i+2] a a[2i+3] určia charakteristiky zodpovedajúcej hrany. Pre graf s celočíselnými váhami hrán je poradie vo všeobecnosti podobné (jediný rozdiel bude v tom, že atribúty budú sledovať váhu hrany a budú špecifikované prvkami a[2i+3] a a[2i+4] , a samotný okraj bude špecifikovaný nie 4, ale 5 objednanými číslami). A pre graf s neceločíselnými váhami hrán možno vlastnosti zapísať do jeho neváženej zložky.
Pri použití asociatívneho poľa priľahlosti pre grafy s celočíselnými váhami hrán je možné zadať ako hodnotu nie jedno číslo, ale pole (vektor) čísel, ktoré okrem váhy hrany špecifikujú aj všetky jej ďalšie potrebné Vlastnosti. Zároveň bude nevýhodou v prípade neceločíselných váh nutnosť špecifikovať znamienko s číslom s pohyblivou rádovou čiarkou (áno, je to nepríjemnosť, ale ak takýchto znamienok nie je až tak veľa a ak nechcete Nenastavte ich príliš „zložito“ dvakrát, potom to nemusí byť nič). To znamená, že v C++ môžu byť polia rozšírenej asociatívnej susednosti definované takto: std::map , std::vector> alebo std::map , std::vector, v ktorom prvá hodnota v „kľúč-hodnota-vektor“ bude váha hrany a následne sa nachádzajú číselné označenia jej atribútov.
Referencie:
O grafoch a algoritmoch všeobecne:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algoritmy: konštrukcia a analýza, 2. vydanie: Trans. z angličtiny – M.: Williams Publishing House, 2011.
2. Harari Frank. Teória grafov. M.: Mir, 1973.
Autorova správa o tom istom vektore a asociatívnom poli susedností:
3. Chernoukhov S.A. Vektorové a asociatívne pole susedstva ako spôsoby reprezentácie a ukladania grafov / SA Chernouhov. Vektor susedstva a mapa susedstva ako dátové štruktúry na znázornenie grafu // Zbierka článkov medzinárodnej vedeckej a praktickej konferencie „Problémy implementácie výsledkov inovatívneho vývoja a spôsoby ich riešenia“ (Saratov, 14.09.2019. septembra 2019). – Sterlitamak: AMI, 65, s. 69-XNUMX
Užitočné online zdroje na túto tému:
4.
5.
Zdroj: hab.com