Adatstruktúrák grafok tárolására: létező megoldások áttekintése és két „majdnem új”

Helló mindenkinek.

Ebben a bemutatóban felsorolom azokat az adatstruktúrákat, amelyeket a grafok tárolására használnak az informatikában, és beszélek néhány más hasonló struktúráról is, amelyek valamiért „kristályosodtak” bennem.

Nos, kezdjük. De nem az elején – gondolom, mindannyian tudjuk, mi az a graf és milyen típusai vannak (irányított, irányítatlan, súlyozott, nem súlyozott, többszörös élekkel és hurkokkal vagy nélkülük).

Tehát nézzük meg, milyen adatstruktúrák állnak rendelkezésünkre a grafok tárolására.

1. Mátrix alapú adatstruktúrák

1.1 Szomszédsági mátrix. A szomszédsági mátrix egy olyan mátrix, amelynek sor- és oszlopfejlécei a graf csúcsainak számát képviselik, míg az egyes elemeinek értéke a közöttük lévő élek jelenlétét vagy hiányát jelöli a következő képlettel: a(i,j). Nyilvánvaló, hogy az irányítatlan graf esetén ez a mátrix szimmetrikus lesz, vagy pedig megbeszélhetjük, hogy az összes értéket csak a fő átló felett tároljuk. Az irányítatlan grafok esetén a(i,j) az i-ből j-be mutató élek számát jelenti (ha ilyen élt nem találunk, akkor a(i,j)= 0), míg a súlyozott grafok esetén az élek súlyát (összsúlyát) is így lehet megadni.

1.2 Incidencia mátrix. Ez esetben a grafunk is egy táblázatban tárolódik, amelyben általában a sorok számának a csúcsok számai, míg az oszlopok számának a korábban számozott élek felelnek meg. Ha egy csúcs és egy él incidens egymásra, akkor a megfelelő cellában egy nem nulla érték kerül rögzítésre (irányítatlan grafok esetén 1 kerül beírásra, ha a csúcs és az él incidensek, irányított grafok esetében pedig „1”, ha az él „kilép” a csúcsból és „-1”, ha „belép” a csúcsba (ezt elég könnyen megjegyezhetjük, mert a „mínusz” jel is úgy „belép” a „-1” számba)). A súlyozott grafok esetén a 1 és -1 helyett a súly az, amit használunk.

2. Értékelő adatstruktúrák

2.1 Szomszédsági lista. Itt úgy tűnik, minden egyszerű. Minden gráfcsúcsnak, általában véve, bármilyen enumeratív struktúrával (lista, vektor, tömb, ...) megfelelően hozzárendelhető, amelyben az adott csúccsal szomszédos összes csúcs számát tárolják. Az irányított gráfok esetében ebbe a listába csak azokat a csúcsokat fogjuk felvenni, amelyekbe „irányított” él van a jelölő csúcsból. A súlyozott gráfok esetében a megvalósítás bonyolultabb lesz.

2.2 Élek listája. Ez egy meglehetősen népszerű adatstruktúra. Az élek listája, amint azt a Kapitány Nyilvánvaló megmondja, valójában a gráf éleinek saját listáját képviseli, amelyből minden él egy kezdő csúccsal, végső csúccsal (a nem irányított gráfoknál a sorrend nem számít, bár egységesítés céljából különböző szabályokat használhatunk, például a csúcsokat növekvő sorrendbe állítva) és súlyjal (csak a súlyozott gráfok számára) van meghatározva.

A fent említett listák-mátrixok részletesen (és illusztrációkkal) megtekinthetők, például itt.

2.3 Szomszédsági mátrix. Nem a leggyakrabban előforduló struktúra. Valójában egyfajta „csomagolási” formát képvisel a szomszédsági listák egy enumeratív struktúrába (tömb, vektor) történő összegyűjtésének. A gráf csúcsainak számához tartozó első n eleme ennek a tömbnek a kezdő indexeit tartalmazza, amelyek a következő csúcsokat tartalmazzák, amelyek szomszédosak az adott csúccsal.

Itt találtam a legérthetőbb (saját számomra) magyarázatot: ejuo.livejournal.com/4518.html

3. Szomszédsági vektor és asszociatív szomszédsági tömb

Úgy alakult, hogy a sorok szerzője, aki nem profi programozó, de időnként foglalkozott gráfokkal, leggyakrabban az élek listáival találkozott. Valóban hasznos, ha a gráfban többszörös hurok és él van. És itt, az klasszikus élek listáinak kiterjesztése érdekében, javaslom, hogy figyelmet szenteljünk a „kibővítésük/növekedésük/módosításuk/mutációjuk” irányába, nevezetesen: a szomszédsági vektorra és asszociatív szomszédsági tömbre.

3.1 Szomszédsági vektor

Eset (a1): nem súlyozott gráf

A nem súlyozott gráf szomszédsági vektorának fogjuk nevezni a páros számú egész számokat tartalmazó rendezett halmazt (a[2i], a[2i+1],..., ahol i 0-tól kezdődik), amelyben minden szám pár a[2i], a[2i+1] egy él gráf között a a[2i] és a[2i+1] csúcsok között.
Ez a felvételi formátum nem tartalmaz információt arról, hogy a gráf irányított-e (mindkét lehetőség megengedett). Amikor ezt a formátumot irányított gráfként használják, a szegmens úgy tekintendő, hogy az a[2i]-ből a a[2i+1]-be irányul. Itt és a továbbiakban: nem irányított gráfok esetén, ha szükséges, alkalmazhatók a csúcsok rögzítési sorrendjére vonatkozó követelmények (például, hogy az első a kisebb számértékkel rendelkező csúcs legyen).

C++-ban a szomszédsági vektort érdemes std::vector használatával definiálni, ezért választották ezt az adattípus nevét.

Eset (a2): súlyozatlan gráf, az élek súlyai egész számok.

Hasonlóan az (a1) esethez, a súlyozott gráf szomszédsági vektorát egész számú él súlyokkal úgynevezett rendezett sorozatnak (dinamikus tömb) nevezzük (a[3i], a[3i+1], a[3i+2],…, ahol i 0-tól kezdődik), ahol minden "triplet" szám a[3i], a[3i+1], a[3i+2] a gráf élét határozza meg a a[3i] és a[3i+1] számú csúcsai között, a a[3i+2] pedig ennek az élnek a súlyát adja. Ez a gráf szintén lehet irányított vagy nem.

Eset (b): súlyozatlan gráf, az élek súlyai nem egész számok.

Mivel egy tömbben (vektorban) nem tárolhatók vegyes elemek, lehetséges például a következő implementáció. A gráf egy pár vektorban tárolódik, ahol az első vektor a gráf szomszédsági vektora, amely nem tartalmazza a súlyokat, míg a második vektor a megfelelő súlyokat tartalmazza (lehetséges implementáció C++-ban: std::pair). Így az él, amely két csúcs párjával van meghatározva az első vektor 2i, 2i+1 indexein, súlya az i indexű elem lesz a második vektorban.

De miért van erre szükség?

Nos, ennek a szövegnek a szerzője számos feladat megoldásához ezt elég hasznosnak találta. Formális szempontból az alábbi előnyök származnak ebből:

• A szomszédsági vektor, akárcsak bármilyen más "felsorolásos" struktúra, elég kompakt, kevesebb memóriát foglal el, mint a szomszédsági mátrix (sparsz gráfok esetén), viszonylag könnyen megvalósítható.
• A gráf csúcsai elvileg negatív számokkal is megjelölhetők. Lehet, hogy szükség lesz egy ilyen "perverzióra" is.
• A gráfok tartalmazhatnak többszörös éleket és többszörös hurokakat, különböző súlyokkal (pozitív, negatív, sőt nullák is). Nincsenek korlátozások.
• A bordákhoz különböző tulajdonságokat is rendelhetünk – erről lásd a 4. pontot.

Ugyanakkor el kell ismerni, hogy a listának nincs gyors hozzáférése a bordához. Itt jön a segítségünkre a Szigetelő asszociatív tömb, amiről alább olvashat.

3.2 Szigetelő asszociatív tömb

Tehát, ha a konkrét élhez, annak súlyához és egyéb tulajdonságaihoz való hozzáférés kritikusan fontos számunkra, és a memóriaigények nem teszik lehetővé a szomszédsági mátrix használatát, gondoljuk végig, hogyan tudnánk megváltoztatni a szomszédsági vektort e probléma megoldására. Tehát a kulcs az él a gráfban, amelyet rendezett egész számok párjaként lehet definiálni. Mire hasonlít ez? Nem egy kulcsra az asszociatív tömbben? Ha igen, akkor miért ne valósítanánk meg? Legyen egy ilyen asszociatív tömbünk, ahol minden kulcshoz – rendezett egész szám párhoz – tartozik egy érték – egész vagy valós szám, amely az él súlyát jelöli. C++-ban érdemes ezt a struktúrát a std::map konténer alapján megvalósítani (std::map<std::pair, int> vagy std::map<std::pair, double>), vagy std::multimap, ha több él várható. Nos, így létrehoztuk a gráfok tárolásához megfelelő struktúrát, amely kevesebb memóriát foglal el, mint a "mátrix" struktúrák, képes kezelni a többszörös hurkokat és éleket, sőt, a csúcsok nemnegatív számainak szigorú követelményei sincsenek (nem tudom, kinek van szüksége erre, de mégis).

4. Adatszerkezetek, bár "beletöltheted", valami hiányzik

Valóban: számos feladat megoldásakor szükségünk lehet arra, hogy a gráf éleihez különféle jellemzőket rendeljünk, és ennek megfelelően tároljuk őket. Ha ezeket a jellemzőket egyértelműen egész számokká lehet redukálni, akkor ilyen "kiegészített jellemzőkkel rendelkező gráfokat" tárolhatunk a kibővített szomszédsági vektorok és az asszociatív szomszédsági tömbök használatával.

Tegyük fel, hogy van egy súlyozatlan gráfunk, ahol minden élhez például 2 további jellemzőt kell tárolni, amelyek egész számokkal vannak megadva. Ebben az esetben az élek szomszédos vektorát úgy definiálhatjuk, mint rendezett egész számok halmazát, amely nem "párokból", hanem "négyesekből" áll (a[2i], a[2i+1], a[2i+2], a[2i+3]…), ahol a[2i+2] és a[2i+3] határozzák meg a megfelelő él jellemzőit. A súlyozott élek esetében a sorrend alapvetően hasonló (a különbség csupán annyi, hogy a jellemzők az él súlya után következnek, és a a[2i+3] és a[2i+4] elemek határozzák meg őket, míg magát az élt nem 4, hanem 5 rendezett szám határozza meg). Az élek nem egész számú súlyainak esetében a jellemzők a súlyozatlan komponensében is rögzíthetők.

Az asszociatív szomszédsági tömb használatakor súlyozott élek esetén nemcsak egy külön szám, hanem egy számokból álló tömb (vektor) is megadható, amely az él súlya mellett minden egyéb szükséges jellemzőt is meghatároz. Nem egész számú súlyok esetén azonban kényelmetlenséget jelent az, hogy a jellemzőt lebegőpontos számmal kell megadni (igen, ez kényelmetlenség, de ha az ilyen jellemzők nem túl sokan vannak, és ha nem túl "bonyolult" double-t adunk meg, akkor talán nem olyan nagy probléma). Így a C++-ban az asszociatív szomszédsági tömbök a következőképpen definiálhatók: std::map <std::pair , std::vector> vagy std::map <std::pair , std::vector>, ahol a "kulcs-érték vektorában" az első érték az él súlya, majd pedig a jellemzők numerikus megjelölései következnek.

Irodalom:

A gráfokkal és algoritmusokkal általában:

1. Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford. Algoritmusok: kialakítás és elemzés, 2. kiadás: Angolról fordítva – M.: Williams Kiadó, 2011.
2. Harari, Frank. A gráfok elmélete. M.: Mir, 1973.
Az író előadása erről a vektorról és asszociatív tömbről:
3. Chernouhov S.A. Adjacency vector and adjacency map as methods of representing and storing graphs / S.A. Chernouhov. Adjacency vector and adjacency map as data structures to represent a graph // Collection of articles from the International Scientific and Practical Conference "Problems of implementing innovative developments and ways to solve them" (Saratov, 14.09.2019). – Sterlitamak: AMI, 2019, pp. 65-69
Hasznos internetes források a témában:
4. prog-cpp.hu/adat-graf
5. ejuo.livejournal.com/4518.html

Forrás: habr.com