Üdvözlet mindenkinek.
Ebben a jegyzetben úgy döntöttem, hogy felsorolom a számítástechnikában a grafikonok tárolására használt főbb adatstruktúrákat, és beszélek még pár ilyen struktúráról, amelyek valahogy „kikristályosodtak” számomra.
Szóval, kezdjük. De nem a kezdetektől fogva – szerintem már mindannyian tudjuk, mi az a gráf, és mi az (irányított, irányítatlan, súlyozott, súlyozatlan, több éllel és hurokkal vagy anélkül).
Akkor gyerünk. Milyen lehetőségeink vannak a „grafikon tárolására” szolgáló adatstruktúrákra?
1. Mátrix adatszerkezetek
1.1 Szomszédsági mátrix. A szomszédsági mátrix egy olyan mátrix, ahol a sor- és oszlopfejlécek megfelelnek a gráf csúcsainak számának, és minden elemének a(i,j) értékét a csúcsok közötti élek megléte vagy hiánya határozza meg. i és j (nyilvánvaló, hogy irányítatlan gráf esetén egy ilyen mátrix szimmetrikus lesz, vagy megegyezhetünk abban, hogy minden értéket csak a főátló felett tárolunk). Súlyozatlan gráfoknál az a(i,j) beállítható az i-től j-ig tartó élek számával (ha nincs ilyen él, akkor a(i,j)= 0), súlyozott gráfoknál pedig a súllyal is (teljes tömeg) az említett élek.
1.2 Előfordulási mátrix. Ebben az esetben a gráfunkat is egy táblázatban tároljuk, amelyben főszabály szerint a sorszámok a csúcsainak számai, az oszlopok pedig az előre számozott éleknek felelnek meg. Ha egy csúcs és egy él beesik egymásra, akkor a megfelelő cellába nullától eltérő értéket írunk (irányítatlan gráfok esetén 1-et írunk, ha a csúcs és az él incidens, orientált gráfoknál - „1”, ha az él „kilép” a csúcsból, és „-1”, ha „benne van” (elég könnyű megjegyezni, mert úgy tűnik, hogy a „mínusz” jel is „benne van” a „-1” számban). Súlyozott gráfoknál ismét az 1 és a -1 helyett megadhatja az él teljes súlyát.
2. Felsorolási adatszerkezetek
2.1 Szomszédsági lista. Nos, itt minden egyszerűnek tűnik. A gráf minden csúcsához általában hozzá lehet rendelni bármilyen felsorolási struktúrát (lista, vektor, tömb, ...), amely az adott csúcshoz tartozó összes csúcs számát tárolja. Irányított gráfok esetén csak azokat a csúcsokat adjuk hozzá egy ilyen listához, amelyekhez egy jellemzőcsúcsból „irányított” él van. Súlyozott grafikonok esetében a megvalósítás bonyolultabb lesz.
2.2 A bordák listája. Elég népszerű adatstruktúra. Az élek listája, amint azt Captain Obviousness mondja, valójában a gráf éleinek listája, amelyek mindegyikét a kezdőcsúcs, a végcsúcs határozza meg (iránytalan gráfoknál a sorrend itt nem fontos, bár az egységesítéshez különböző szabályokat használjon, például a csúcsok megadását növekedési sorrendben és súlyt (csak súlyozott gráfokhoz).
A fent felsorolt mátrix listákat részletesebben (és illusztrációkkal) megtekintheti, pl. .
2.3 Szomszédsági tömb. Nem a leggyakoribb szerkezet. Lényegében a szomszédsági listák „csomagolása” egyetlen felsorolási struktúrába (tömb, vektor). Egy ilyen tömb első n (a gráf csúcsainak száma szerint) eleme tartalmazza ugyanannak a tömbnek a kezdőindexeit, ahonnan kiindulva sorba írjuk az összes szomszédos csúcsot.
Itt találtam a (magam számára) legérthetőbb magyarázatot:
3. Szomszédsági vektor és asszociatív szomszédsági tömb
Kiderült, hogy e sorok írója, nem lévén profi programozó, de rendszeresen foglalkozott gráfokkal, legtöbbször éllistákkal foglalkozott. Valóban kényelmes, ha a gráf több hurokkal és éllel rendelkezik. Így a klasszikus éllisták kidolgozásakor azt javaslom, hogy fordítsunk figyelmet a „fejlődésükre/elágazásukra/módosításukra/mutációjukra”, nevezetesen: a szomszédsági vektorra és az asszociatív szomszédsági tömbre.
3.1 Szomszédsági vektor
(a1) eset: súlyozatlan grafikon
Egy súlyozatlan gráf szomszédsági vektorának nevezzük páros számú egész szám rendezett halmazát (a[2i], a[2i+1],..., ahol i számozása c 0), amelyben minden számpár az a[2i], az a[2i+1 ] egy gráfélt ad meg az a[2i] és a[2i+1] csúcsok között.
Ez a rögzítési formátum nem tartalmaz információt arról, hogy a grafikon irányított-e (mindkét lehetőség lehetséges). A digráf formátum használatakor az élt a[2i]-ből a[2i+1]-be irányítottnak tekintjük. Itt és lent: irányítatlan gráfoknál szükség esetén a csúcsok rögzítésének sorrendjére vonatkozó követelmények alkalmazhatók (például, hogy a hozzárendelt szám kisebb értékű csúcsa legyen az első).
C++-ban célszerű egy szomszédsági vektort megadni az std::vector használatával, innen ered ennek az adatszerkezetnek a neve.
(a2) eset: súlyozatlan gráf, az élsúlyok egészek
Az (a1) esethez hasonlóan a szomszédsági vektort egész élsúlyú súlyozott gráfhoz számok rendezett halmazának (dinamikus tömbjének) nevezzük (a[3i], a[3i+1], a[3i+2], ..., ahol i számozása c 0), ahol az a[3i], a[3i+1], a[3i+2] számok mindegyik „hármasa” a gráf egy élét adja meg az a[3i] számú csúcsok között. és a[3i+1], és az a [3i+2] érték ennek az élnek a súlya. Egy ilyen gráf lehet irányított vagy nem is.
(b) eset: súlyozatlan gráf, nem egész számú élsúlyozás
Mivel például lehetetlen heterogén elemeket egy tömbben (vektorban) tárolni, a következő megvalósítás lehetséges. A gráf egy vektorpárban van tárolva, amelyben az első vektor a gráf szomszédsági vektora a súlyok megadása nélkül, a második vektor pedig a megfelelő súlyokat tartalmazza (lehetséges megvalósítás C++ esetén: std::pair ). Így az első vektor 2i, 2i+1 indexe alatti csúcspár által meghatározott él esetén a súly egyenlő lesz a második vektor i indexe alatti elemmel.
Nos, miért van erre szükség?
Nos, e sorok írója igen hasznosnak találta számos probléma megoldásában. Nos, formai szempontból a következő előnyökkel jár:
- A szomszédsági vektor, mint bármely más „felsoroló” struktúra, meglehetősen kompakt, kevesebb memóriát foglal, mint a szomszédsági mátrix (ritka gráfok esetén), és viszonylag könnyen megvalósítható.
- A gráf csúcsai elvileg negatív számokkal is jelölhetők. Mi van, ha egy ilyen „perverzióra” van szükség?
- A grafikonok több élt és több hurkot is tartalmazhatnak, különböző súllyal (pozitív, negatív, akár nulla). Itt nincsenek korlátozások.
- Az élekhez különböző tulajdonságokat is rendelhet – de erről bővebben a 4. részben olvashat.
Azonban el kell ismerni, hogy ez a „lista” nem jelent gyors hozzáférést a peremhez. És itt az Associative Adjacency Array jön a megmentésre, amelyet alább tárgyalunk.
3.2 Asszociatív szomszédsági tömb
Tehát, ha egy adott élhez való hozzáférés, annak súlya és egyéb tulajdonságai kritikusak számunkra, és a memóriaigények nem teszik lehetővé a szomszédsági mátrix használatát, akkor gondoljuk át, hogyan változtathatjuk meg a szomszédsági vektort a probléma megoldására. Tehát a kulcs a gráf egy éle, amely egy rendezett egész számpárként adható meg. Hogy néz ez ki? Nem kulcs egy asszociatív tömbben? És ha igen, miért nem valósítjuk meg? Legyen egy asszociatív tömbünk, ahol minden kulcshoz - egy rendezett egész számpárhoz - egy értékhez lesz rendelve - egy egész vagy egy valós szám, amely meghatározza az él súlyát. C++ nyelven ezt a struktúrát az std::map konténer (std::map) alapján célszerű megvalósítani , int> vagy std::map , double>), vagy std::multimap, ha több él várható. Nos, a gráfok tárolására olyan struktúránk van, amely kevesebb memóriát foglal, mint a „mátrix” struktúrák, több hurokkal és élekkel definiálható gráfokat, és még a csúcsszámok nem-negativitására sem támaszt szigorú követelményeket (nem tudom kinek kell ez, de mégis).
4. Az adatstruktúrák megteltek, de valami hiányzik
És ez igaz: számos probléma megoldása során előfordulhat, hogy a gráf éleihez néhány jellemzőt kell rendelnünk, és ennek megfelelően el kell tárolnunk azokat. Ha lehetséges ezeket a jellemzőket egyértelműen egész számokra redukálni, akkor lehetséges az ilyen „kiegészítő tulajdonságokkal rendelkező grafikonok” tárolása a szomszédsági vektor és az asszociatív szomszédsági tömb kiterjesztett verzióival.
Legyen tehát egy súlyozatlan gráfunk, amelynek minden élére szükség van például 2 további, egész számokkal meghatározott jellemző tárolására. Ebben az esetben a szomszédsági vektorát nem „párok”, hanem egész számok „kvartettjei” (a[2i], a[2i+1], a[2i+2], a) rendezett halmazaként definiálhatjuk. [2i+3]…) , ahol a[2i+2] és a[2i+3] határozza meg a megfelelő él jellemzőit. Az élek egész súlyú gráfjainál a sorrend általában hasonló (az egyetlen különbség az lesz, hogy az attribútumok követik az él súlyát, és az a[2i+3] és a[2i+4] elemek határozzák meg őket. , és maga az él nem 4, hanem 5 rendezett szám lesz megadva). A nem egész élsúlyú gráfok esetében pedig a jellemzők a súlyozatlan komponensébe írhatók.
Ha asszociatív szomszédsági tömböt használunk egész élsúllyal rendelkező gráfokhoz, akkor lehetőség van értékként nem egyetlen szám megadására, hanem számokból álló tömb (vektor) megadására, amely az él súlyán túlmenően megadja annak minden egyéb szükségességét is. jellemzők. Ugyanakkor a nem egész súlyok esetében kényelmetlenséget okoz, hogy lebegőpontos számot kell megadni (igen, ez kellemetlen, de ha nincs olyan sok ilyen jel, és ha nem ne állítsa be őket túl „trükkös” duplán, akkor lehet, hogy nem lesz semmi) . Ez azt jelenti, hogy a C++ kiterjesztett asszociatív szomszédsági tömbök a következőképpen definiálhatók: std::map , std::vector> vagy std::map , std::vector, amelyben a „kulcsérték-vektor” első értéke az él súlya lesz, majd a jellemzőinek numerikus jelölései találhatók.
irodalom:
A grafikonokról és az algoritmusokról általában:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algoritmusok: szerkesztés és elemzés, 2. kiadás: Ford. angolról – M.: Williams Kiadó, 2011.
2. Harari Frank. Gráfelmélet. M.: Mir, 1973.
A szerző beszámolója ugyanezekről a vektorokról és a szomszédosságok asszociatív tömbjéről:
3. Chernoukhov S.A. Szomszédsági vektor és asszociatív szomszédsági tömb, mint a grafikonok ábrázolásának és tárolásának módjai / SA Chernouhov. Szomszédsági vektor és szomszédsági térkép, mint adatszerkezetek grafikon ábrázolásához // Az „Innovatív fejlesztések eredményeinek megvalósításának problémái és megoldási módjai” (Saratov, 14.09.2019. szeptember 2019.) Nemzetközi Tudományos és Gyakorlati Konferencia cikkgyűjteménye. – Sterlitamak: AMI, 65, p. 69-XNUMX
Hasznos online források a témában:
4.
5.
Forrás: will.com