Ahoj všichni.
V tomto příspěvku jsem se rozhodl vyjmenovat hlavní datové struktury používané pro ukládání grafů v informatice, a také se zmínit o dalších dvou takových strukturách, které se mi nějak samy „vykrystalizovaly“.
Tak tedy začněme. Ale ne úplně od začátku – myslím, že co je graf a jaké máme varianty (oriented, neoriented, weighted, unweighted, s více hranami a smyčkami nebo bez nich), už všichni známe.
Tak jdeme na to. Jaké možnosti datových struktur pro „grafové ukládání“ máme.
1. Maticové datové struktury
1.1 Matrice sousednosti. Matrice sousednosti představuje matici, kde hlavičky řádků a sloupců odpovídají číslům vrcholů grafu, a samotná hodnota každého jejího prvku a(i,j) je určena přítomností nebo nepřítomností hran mezi vrcholy i a j (jasně, pro neorientovaný graf bude taková matice symetrická, nebo se můžeme dohodnout, že všechny hodnoty uchováváme pouze nad hlavní diagonálou). Pro neweighted grafy může být a(i,j) stanoveno počtem hran z i do j (pokud taková hrana neexistuje, pak a(i,j)= 0), a pro weighted také – váhou (celkovou váhou) zmíněných hran.
1.2 Matice incidenčnosti. V tomto případě náš graf také spočívá v tabulce, kde obvykle číslům řádků odpovídají čísla jeho vrcholů a číslům sloupců – předem číslované hrany. Pokud je vrchol a hrana incidentní, pak se v odpovídající buňce zapisuje nenulová hodnota (pro neorientované grafy se zapisuje 1 v případě incidentnosti vrcholu a hrany, pro orientované – „1“, pokud hrana „vychází“ z vrcholu, a „-1“, pokud do něj „vstupuje“ (pamatuje se to dost snadno, neboť znaménko „mínus“ také jakoby „vstupuje“ do čísla „-1“)). Pro weighted grafy můžeme opět místo 1 a -1 uvádět celkovou váhu hrany.
2. Výčtové datové struktury
2.1 Seznam sousednosti. Zdá se, že je vše jednoduché. Každému vrcholu grafu můžeme v obecnosti přiřadit jakoukoli enumerativní strukturu (seznam, vektor, pole, …), ve které budou uchovávány čísla všech sousedních vrcholů daného. Pro orientované grafy budeme do takového seznamu zapisovat pouze ty vrcholy, do kterých vede „orientovaná“ hrana z vrcholu-příznaku. Pro vážené grafy bude implementace složitější.
2.2 Seznam hran. Poměrně populární datová struktura. Seznam hran, jak nám napovídá kapitán zřejmosti, představuje seznam hran grafu, z nichž každá je určena počátečním vrcholem, koncovým vrcholem (u neorientovaných grafů zde pořadí následování není důležité, ačkoli pro unifikaci lze použít různá pravidla, například uvádět vrcholy v rostoucím pořadí) a váhou (pouze pro vážené grafy).
O výše zmíněných seznamech-maticích se můžete podívat podrobněji (a s ilustracemi), např. .
2.3 Pole sousednosti. Není to zrovna běžná struktura. V podstatě představuje formu „obalu“ seznamů sousednosti v jednu enumerativní strukturu (pole, vektor). Prvních n (podle počtu vrcholů grafu) prvků takového pole obsahuje počáteční indexy daného pole, od kterých jsou v něm postupně zapsány všechny vrcholy sousední dané.
Tady jsem našel nejvíce srozumitelné (pro sebe) vysvětlení:
3. Vektor sousednosti a Asociativní pole sousednosti
Stalo se tak, že autor těchto řádků, ačkoli není profesionálním programátorem, občas měl co do činění s grafy, často se zabýval seznamy hran. Opravdu, je to pohodlné, pokud má graf více smyček a hran. A tak, v rozvoji klasických seznamů hran, navrhuji věnovat pozornost i jejich „rozvoji/odvětvení/modifikaci/mutaci“, konkrétně: vektoru sousednosti a asociativnímu poli sousednosti.
3.1 Vektor sousednosti
Případ (a1): nevážený graf
Budeme nazývat vektorem sousednosti pro nevážený graf uspořádaný soubor sudého počtu celých čísel (a[2i], a[2i+1],…, kde i je číslováno od 0), ve kterém každá dvojice čísel a[2i], a[2i+1] určuje hranu grafu mezi vrcholy a[2i] a a[2i+1] respektive.
Tento formát zápisu neobsahuje informace o tom, zda je graf orientovaný (jsou možné obě varianty). Při použití formátu pro orientovaný graf se předpokládá, že hrana směřuje z a[2i] do a[2i+1]. Zde a dále: pro neorientované grafy, pokud je to nutné, lze uplatnit požadavky na pořadí zápisu vrcholů (například aby prvním byl vrchol s menší přidělenou hodnotou čísla).
Ve C++ je účelné reprezentovat sousední vektory pomocí std::vector, odtud bylo zvoleno název této datové struktury.
Případ (a2): nevyvážený graf, váhy hran jsou celočíselné
Analogicky k případu (a1) nazveme sousedním vektorem pro vyvážený graf s celočíselnými váhami hran uspořádanou množinu (dynamické pole) čísel (a[3i], a[3i+1], a[3i+2],…, kde i je číslováno od 0), kde každý 'triplet' čísel a[3i], a[3i+1], a[3i+2] určuje hranu grafu mezi vrcholy s čísly a[3i] a a[3i+1] a hodnota a[3i+2] je váha této hrany. Takový graf může být jak orientovaný, tak ne.
Případ (b): nevyvážený graf, váhy hran nejsou celočíselné
Vzhledem k tomu, že v jednom poli (vektoru) nelze ukládat heterogenní prvky, je možné například následující provedení. Graf je uložen ve dvou vektorech, kde první vektor je sousední vektor grafu bez vyznačení vah, a druhý vektor obsahuje odpovídající váhy (možná realizace pro C++: std::pair). Tímto způsobem, pro hranu určenou pár vrcholů s indexy 2i, 2i+1 v prvním vektoru, bude váha rovna prvku s indexem i druhého vektoru.
Ale k čemu to je?
Autorovi těchto řádků se to pro řešení několika úkolů zdálo dost užitečné. A z formálního hlediska tu budou takové výhody:
- Sousední vektor, stejně jako jakákoli jiná 'vyjmenovaná' struktura, je dost kompaktní, zaujímá méně paměti než matice sousedství (pro řídké grafy), relativně jednoduše se realizuje.
- Vrcholům grafu mohou být v zásadě přidělena i záporná čísla. Kdyby to náhodou potřeba i taková 'úchylka'.
- Grafy mohou obsahovat mnohonásobné hrany a mnohonásobné smyčky, přičemž s různými váhami (kladné, záporné, dokonce i nulové). Žádná omezení zde nejsou.
- A také lze hranám přiřazovat různé vlastnosti – viz bod 4.
Je však třeba uznat, že tato "seznamová struktura" nepředpokládá rychlý přístup k hraně. A zde nám přichází na pomoc asociativní pole sousednosti, o kterém bude řeč níže.
3.2 Asociativní pole sousednosti
Pokud je pro nás přístup ke konkrétní hraně, její hmotnosti a jiným vlastnostem zásadní, a požadavky na paměť nám neumožňují použít matici sousednosti, zkusme přemýšlet, jak lze změnit vektor sousednosti, abychom tento úkol vyřešili. Klíčem je hrana grafu, kterou lze zapsat jako uspořádanou dvojici celých čísel. Na co to však vypadá? Není to klíč v asociativním poli? A pokud ano, proč to neimplementovat? Předpokládejme, že máme takové asociativní pole, kde každému klíči – uspořádané dvojici celých čísel – bude přiřazena hodnota – celé nebo reálné číslo, které určuje hmotnost hrany. V C++ je vhodné implementovat tuto strukturu na základě kontejneru std::map (std::map <std::pair , int> nebo std::map <std::pair , double>), nebo std::multimap, pokud se předpokládají vícehrany. A tak, máme strukturu pro ukládání grafů, která zabírá méně paměti než "maticové" struktury, může definovat grafy s vícero smyčkami a hranami a dokonce nemá přísné požadavky na nezáporné číslo vrcholů (nevím, kdo to potřebuje, ale přesto).
4. Struktury dat, ať už "naplníš", něco chybí
A je to pravda: při řešení některých úloh může nastat potřeba přidělit hranám grafu určité vlastnosti a následně je uchovávat. Pokud lze tyto vlastnosti jednoznačně převést na celá čísla, pak lze uchovávat takové "grafy s dodatečnými vlastnostmi" pomocí rozšířených verzí vektoru sousednosti a asociativního pole sousednosti.
Mějme tedy nevyvážený graf, pro každou hranu kterého je nutné uchovávat například 2 další atributy definované celými čísly. V takovém případě lze jeho sousední vektor definovat jako uspořádanou množinu nikoli "párů", ale "kvartetů" celých čísel (a[2i], a[2i+1], a[2i+2], a[2i+3]…), kde a[2i+2] a a[2i+3] budou definovat atributy odpovídající hrany. Pro graf se celými váhami hran je pořadí v zásadě podobné (liší se pouze tím, že atributy budou následovat za váhou hrany a budou definovány prvky a[2i+3] a a[2i+4], přičemž samotná hrana bude definována nikoli 4, ale 5 uspořádanými čísly). A pro graf s neceločíselnými váhami hran mohou být atributy zapsány v jeho nevyvážené komponentě.
Při použití asociativního pole sousednosti pro grafy s celými váhami hran je možné jako hodnotu definovat nikoli jednotlivé číslo, ale pole (vektor) čísel, které určují vedle váhy hrany všechny ostatní nezbytné atributy. V tomto případě je nevýhodou pro předpoklad neceločíselných vah nutnost definice atributu jako čísla s plovoucí desetinnou čárkou (ano, to je nevýhoda, ale pokud těchto atributů není příliš mnoho, a pokud je nebudeme definovat příliš "chytře" jako double, tedy to možná nebude tak zlé). A tedy v C++ mohou být rozšířená asociativní pole sousednosti definována následujícím způsobem: std::map <std::pair , std::vector> nebo std::map <std::pair , std::vector, přičemž prvním prvkem v "vektoru-hodnotě-podle-klíče" bude váha hrany a dále se nacházejí číselné označení jeho atributů.
Literatura:
O grafech a algoritmech obecně:
1. Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford. Algoritmy: konstrukce a analýza, 2. vydání: Překlad z angličtiny – M.: Vydavatelský dům "Williams", 2011.
2. Harari, Frank. Teorie grafů. M.: Mir, 1973.
Prezentace autora o tomto vektoru a asociativním poli sousednosti:
3. Černoukh S.A. Vektor sousednosti a asociativní mapa sousednosti jako způsoby reprezentace a ukládání grafů / S.A. Černoukh. Vektor sousednosti a mapa sousednosti jako datové struktury pro reprezentaci grafu // Sborník článků mezinárodní vědecko-praktické konference „Problémy zavádění výsledků inovativních vývojů a cesty jejich řešení“ (Saratov, 14.09.2019). – Sterlitamak: AMI, 2019, s. 65-69
Užitečné internetové zdroje k tématu:
4.
5.
Zdroj: habr.com
