Sveiki visi.
Šioje pastaboje nusprendžiau išvardyti pagrindines duomenų struktūras, naudojamas grafams saugoti informatikos srityje, taip pat pakalbėsiu apie dar porą tokių struktūrų, kurios man kažkaip „iškristalizavosi“.
Taigi, pradėkime. Bet ne nuo pat pradžių – manau, kad visi jau žinome, kas yra grafikas ir kas jis yra (nukreiptas, neorientuotas, svertinis, nesvertinis, su keliomis briaunomis ir kilpomis arba be jų).
Taigi, eime. Kokias duomenų struktūrų galimybes „grafų saugojimui“ turime?
1. Matricinių duomenų struktūros
1.1 Gretimosi matrica. Gretimumo matrica yra matrica, kurioje eilučių ir stulpelių antraštės atitinka grafiko viršūnių skaičius, o kiekvieno jos elemento a(i,j) reikšmė nustatoma pagal briaunų buvimą arba nebuvimą tarp viršūnių. i ir j (aišku, kad nenukreiptam grafikui tokia matrica bus simetriška, arba galime susitarti, kad visas reikšmes saugome tik virš pagrindinės įstrižainės). Nesvertiniams grafams a(i,j) galima nustatyti briaunų skaičiumi nuo i iki j (jei tokios briaunos nėra, tai a(i,j)= 0), o svertiniams grafams taip pat pagal svorį (bendras svoris) minėtų briaunų.
1.2 Sergamumo matrica. Šiuo atveju mūsų grafikas taip pat saugomas lentelėje, kurioje, kaip taisyklė, eilučių numeriai atitinka jos viršūnių skaičius, o stulpelių numeriai – iš anksto sunumeruotas briaunas. Jei viršūnė ir briauna krinta viena į kitą, tada atitinkamame langelyje įrašoma ne nulis reikšmė (nekryptintiems grafams rašoma 1, jei viršūnė ir briauna yra kritimo, orientuotiems grafams - "1", jei briauna „išeina“ iš viršūnės ir „-1“, jei joje „įeina“ (pakankamai lengva atsiminti, nes „minuso“ ženklas taip pat atrodo „įtrauktas“ į skaičių „-1“). Svertiniuose grafikuose vietoj 1 ir -1 galite nurodyti bendrą briaunos svorį.
2. Sąrašų duomenų struktūros
2.1 Gretimybių sąrašas. Na, atrodo, kad čia viskas paprasta. Kiekviena grafo viršūnė paprastai gali būti susieta su bet kokia sąrašo struktūra (sąrašas, vektorius, masyvas, ...), kurioje bus saugomi visų viršūnių, esančių šalia duotosios, skaičius. Nukreiptiems grafams į tokį sąrašą įtrauksime tik tas viršūnes, į kurias yra „nukreipta“ briauna iš požymio viršūnės. Svertinių grafikų įgyvendinimas bus sudėtingesnis.
2.2 Šonkaulių sąrašas. Gana populiari duomenų struktūra. Briaunų sąrašas, kaip mums sako Captain Obviousness, iš tikrųjų yra grafo briaunų sąrašas, kurių kiekvieną nurodo pradinė viršūnė, pabaigos viršūnė (neorientuotiems grafams tvarka čia nėra svarbi, nors suvienodinant galite naudokite įvairias taisykles, pavyzdžiui, nurodykite viršūnes didėjimo tvarka) ir svorį (tik svertiniams grafikams).
Galite pažvelgti į aukščiau pateiktus matricų sąrašus išsamiau (ir su iliustracijomis), pavyzdžiui, .
2.3 Gretimų masyvas. Ne labiausiai paplitusi struktūra. Iš esmės tai yra gretimų sąrašų „pakavimo“ forma į vieną sąrašo struktūrą (masyvą, vektorių). Pirmuosiuose n (pagal grafo viršūnių skaičių) tokio masyvo elementų yra to paties masyvo pradiniai indeksai, nuo kurių iš eilės rašomos visos greta duotosios viršūnės.
Čia radau labiausiai suprantamą (sau) paaiškinimą:
3. Gretumų vektorius ir asociatyvinis gretimų masyvas
Paaiškėjo, kad šių eilučių autorius, nebūdamas profesionalus programuotojas, bet periodiškai dirbęs su grafikais, dažniausiai užsiimdavo briaunų sąrašais. Iš tiesų patogu, jei grafikas turi keletą kilpų ir briaunų. Taigi, kuriant klasikinius briaunų sąrašus, siūlau atkreipti dėmesį į jų „plėtrą/atšaką/modifikaciją/mutaciją“, būtent: gretimų vektorių ir asociatyvų gretimų masyvą.
3.1 Gretimo vektorius
Atvejis (a1): nesvertinis grafikas
Nesvertinio grafo gretimų vektoriumi vadinsime sutvarkytą lyginio skaičiaus sveikųjų skaičių aibę (a[2i], a[2i+1],..., kur i sunumeruota c 0), kurioje kiekviena skaičių pora yra a[2i], a[2i+1 ] nurodo grafo briauną tarp viršūnių a[2i] ir a[2i+1], atitinkamai.
Šiame įrašymo formate nėra informacijos apie tai, ar grafikas yra nukreiptas (galimos abi parinktys). Naudojant dvigrafo formatą, briauna laikoma nukreipta iš a[2i] į a[2i+1]. Čia ir žemiau: nenukreiptiems grafams, jei reikia, gali būti taikomi viršūnių įrašymo eiliškumo reikalavimai (pvz., kad viršūnė su jai priskirto skaičiaus mažesne reikšme būtų pirma).
C++ kalboje patartina nurodyti gretimų vektorių naudojant std::vector, taigi ir šios duomenų struktūros pavadinimas.
Atvejis (a2): nesvertinis grafikas, briaunų svarmenys yra sveikieji skaičiai
Analogiškai su (a1) atveju gretimų vektorių svertiniam grafui su sveikųjų kraštų svoriais vadiname sutvarkyta skaičių aibė (dinaminis masyvas) (a[3i], a[3i+1], a[3i+2], ..., kur i yra sunumeruotas c 0), kur kiekvienas skaičių a[3i], a[3i+1], a[3i+2] „tripletas“ nurodo grafiko kraštą tarp viršūnių, pažymėtų a[3i] ir a[3i+1], o reikšmė a [3i+2] yra šios briaunos svoris. Toks grafikas taip pat gali būti nukreiptas arba ne.
Atvejis (b): nesvertinis grafikas, ne sveikųjų skaičių briaunos svarmenys
Kadangi, pavyzdžiui, viename masyve (vektoriuje) nevienalyčių elementų laikyti neįmanoma, galimas toks įgyvendinimas. Grafas saugomas vektorių poroje, kurioje pirmasis vektorius yra grafiko gretimumo vektorius, nenurodant svorių, o antrame vektoriuje yra atitinkami svoriai (galima C++ realizacija: std::pair ). Taigi briaunos, apibrėžtos viršūnių pora pagal pirmojo vektoriaus indeksus 2i, 2i+1, svoris bus lygus elementui pagal antrojo vektoriaus indeksą i.
Na, kam to reikia?
Na, o šių eilučių autoriui tai buvo gana naudinga sprendžiant daugybę problemų. Na, formaliu požiūriu bus šie pranašumai:
- Gretimumo vektorius, kaip ir bet kuri kita „išvardijimo“ struktūra, yra gana kompaktiška, užima mažiau atminties nei gretimų matrica (retiems grafikams) ir yra gana lengvai įgyvendinama.
- Grafo viršūnės iš esmės taip pat gali būti pažymėtos neigiamais skaičiais. O jeigu reikia tokio „iškrypimo“?
- Grafikuose gali būti kelios briaunos ir kelios kilpos su skirtingu svoriu (teigiamas, neigiamas, net nulis). Čia nėra jokių apribojimų.
- Taip pat briaunoms galite priskirti skirtingas savybes – bet daugiau apie tai žr. 4 skyriuje.
Tačiau reikia pripažinti, kad šis „sąrašas“ nereiškia greito priėjimo prie krašto. Ir čia į pagalbą ateina Associative Adjacency Array, apie kurią kalbama toliau.
3.2 Asociatyvinis gretimų masyvas
Taigi, jei prieiga prie konkretaus krašto, jo svoris ir kitos savybės mums yra labai svarbios, o atminties reikalavimai neleidžia naudoti gretimų matricos, tada pagalvokime, kaip galėtume pakeisti gretumo vektorių, kad išspręstume šią problemą. Taigi, raktas yra grafiko kraštas, kurį galima nurodyti kaip tvarkingą sveikųjų skaičių porą. Kaip tai atrodo? Ar tai ne raktas asociatyviniame masyve? Ir jei taip, kodėl mums to neįgyvendinus? Turėkime asociatyvųjį masyvą, kuriame kiekvienas raktas – tvarkinga sveikųjų skaičių pora – bus susietas su reikšme – sveikuoju skaičiumi arba realiuoju skaičiumi, nurodančiu briaunos svorį. C++ kalboje šią struktūrą patartina įgyvendinti remiantis std::map konteineriu (std::map , int> arba std::map , double>), arba std::multimap, jei tikimasi kelių briaunų. Na, mes turime grafų saugojimo struktūrą, kuri užima mažiau atminties nei „matricos“ struktūros, gali apibrėžti grafikus su keliomis kilpomis ir briaunomis ir net neturi griežtų viršūnių skaičių neneigiamumo reikalavimų (nežinau kam to reikia, bet vis tiek).
4. Duomenų struktūros pilnos, bet kažko trūksta
Ir tai tiesa: sprendžiant daugybę uždavinių, mums gali tekti priskirti kai kurias charakteristikas grafo kraštams ir atitinkamai jas išsaugoti. Jei įmanoma vienareikšmiškai sumažinti šiuos požymius iki sveikųjų skaičių, tai tokius „grafus su papildomomis ypatybėmis“ galima saugoti naudojant išplėstines gretumo vektoriaus ir asociatyvaus gretimų masyvo versijas.
Taigi, turėkime nesvertinį grafiką, kurio kiekvienai briaunai reikia įrašyti, pavyzdžiui, 2 papildomas ypatybes, nurodytas sveikaisiais skaičiais. Šiuo atveju galima apibrėžti jo gretimų vektorių kaip sutvarkytą ne „porų“, o sveikųjų skaičių „kvartetų“ aibę (a[2i], a[2i+1], a[2i+2], a [2i+3]…) , kur a[2i+2] ir a[2i+3] nulems atitinkamos briaunos charakteristikas. Grafo su sveikaisiais kraštinių svoriais tvarka paprastai yra panaši (vienintelis skirtumas bus tas, kad atributai atitiks briaunos svorį ir bus nurodyti elementais a[2i+3] ir a[2i+4] , o pats kraštas bus nurodytas ne 4, o 5 eilės tvarka). O grafo, kurio kraštinių svoriai nėra sveikieji skaičiai, požymius galima įrašyti į nesvertinį komponentą.
Naudojant asociatyvų gretimų masyvą grafams su sveikųjų kraštų svoriais, kaip reikšmę galima nurodyti ne vieną skaičių, o skaičių masyvą (vektorių), kuris, be briaunos svorio, nurodo visas kitas būtinas funkcijos. Tuo pačiu metu, nesveiko skaičiaus svorių atveju, nepatogumų bus poreikis nurodyti ženklą su slankiojo kablelio skaičiumi (taip, tai yra nepatogumas, bet jei tokių ženklų nėra tiek daug ir jei to nepadarysite Nenustatykite jų per daug „keblių“ dvigubų, tada tai gali būti nieko) . Tai reiškia, kad C++ išplėstiniai asociatyvūs gretumo masyvai gali būti apibrėžti taip: std::map , std::vector> arba std::map , std::vektorius, kuriame pirmoji reikšmė „rakto vertės vektoriuje“ bus krašto svoris, o tada pateikiami jo charakteristikų skaitiniai žymėjimai.
Literatūra:
Apie grafikus ir algoritmus apskritai:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algoritmai: konstravimas ir analizė, 2-asis leidimas: Vertimas. iš anglų kalbos – M.: Williams Publishing House, 2011 m.
2. Harari Frank. Grafų teorija. M.: Mir, 1973 m.
Autoriaus pranešimas apie tą patį vektorių ir asociatyvų gretimų masyvą:
3. Chernoukhov S.A. Gretumų vektorius ir asociatyvus gretimų masyvas kaip grafikų vaizdavimo ir saugojimo būdai / SA Chernouhov. Gretumų vektorius ir gretimų žemėlapis kaip duomenų struktūros, skirtos grafikui reprezentuoti // Tarptautinės mokslinės praktinės konferencijos „Inovatyvių plėtros rezultatų įgyvendinimo problemos ir jų sprendimo būdai“ (Saratovas, 14.09.2019 m. rugsėjo 2019 d.) straipsnių rinkinys. – Sterlitamak: AMI, 65, p. 69-XNUMX
Naudingi internetiniai šaltiniai šia tema:
4.
5.
Šaltinis: www.habr.com