Ahoj všichni
V této poznámce jsem se rozhodl uvést hlavní datové struktury používané k ukládání grafů v informatice a budu také mluvit o několika dalších takových strukturách, které mi nějak „vykrystalizovaly“.
Takže, začněme. Ale ne od úplného začátku – myslím, že všichni už víme, co je graf a co to je (orientovaný, neorientovaný, vážený, nevážený, s nebo bez více hran a smyček).
Tak pojďme. Jaké možnosti datových struktur pro „ukládání grafů“ máme?
1. Maticové datové struktury
1.1 Matice sousedství. Matice sousedství je matice, kde záhlaví řádků a sloupců odpovídají číslům vrcholů grafu a hodnota každého z jejích prvků a(i,j) je určena přítomností nebo nepřítomností hran mezi vrcholy. i a j (je jasné, že pro neorientovaný graf bude taková matice symetrická, případně se dohodneme, že všechny hodnoty uložíme pouze nad hlavní diagonálu). U nevážených grafů lze a(i,j) nastavit počtem hran od i do j (pokud taková hrana není, pak a(i,j)= 0) a u vážených grafů také vahou (celková hmotnost) uvedených hran.
1.2 Incidenční matice. V tomto případě je náš graf také uložen v tabulce, ve které zpravidla čísla řádků odpovídají číslům jeho vrcholů a čísla sloupců odpovídají předčíslovaným hranám. Pokud jsou vrchol a hrana navzájem incidentní, pak se do odpovídající buňky zapíše nenulová hodnota (u neorientovaných grafů se zapíše 1, pokud jsou vrchol a hrana incidentní, u orientovaných grafů - „1“, pokud hrana „vystoupí“ z vrcholu a „-1“, pokud do něj „zahrnuje“ (je snadné si to zapamatovat, protože znaménko „mínus“ také vypadá, že je „zahrnuto“ v čísle „-1“)). U vážených grafů opět místo 1 a -1 můžete zadat celkovou váhu hrany.
2. Výčet datových struktur
2.1 Seznam sousedství. No, vše se zdá být jednoduché. Každý vrchol grafu může být obecně spojen s libovolnou výčtovou strukturou (seznam, vektor, pole, ...), ve které budou uložena čísla všech vrcholů sousedících s daným. U orientovaných grafů přidáme do takového seznamu pouze ty vrcholy, ke kterým existuje „nasměrovaná“ hrana z vrcholu prvku. U vážených grafů bude implementace složitější.
2.2 Seznam žeber. Docela populární datová struktura. Seznam hran, jak nám říká Captain Obviousness, je vlastně 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í není důležité, i když pro sjednocení můžete používat různá pravidla, například specifikovat vrcholy v pořadí zvyšování) a váhu (pouze pro vážené grafy).
Na výše uvedené maticové seznamy se můžete podívat podrobněji (a s ilustracemi), např. .
2.3 Pole sousednosti. Není to nejběžnější struktura. Ve svém jádru je to forma „sbalení“ sousedních seznamů do jedné výčtové struktury (pole, vektor). Prvních n (podle počtu vrcholů grafu) prvků takového pole obsahuje počáteční indexy stejného pole, od kterého se zapisují všechny vrcholy sousedící s daným za sebou.
Zde jsem našel nejsrozumitelnější (pro sebe) vysvětlení:
3. Vektor sousednosti a pole asociativních sousedství
Ukázalo se, že autor těchto řádků, který není profesionálním programátorem, ale pravidelně se zabýval grafy, se nejčastěji zabýval seznamy hran. Ve skutečnosti je vhodné, pokud má graf více smyček a hran. A tak při vývoji klasických seznamů hran navrhuji věnovat pozornost jejich „vývoji/větvení/úpravě/mutaci“, a to: vektoru sousednosti a asociativnímu poli sousednosti.
3.1 Vektor sousedství
Případ (a1): nevážený graf
Vektor sousednosti pro nevážený graf budeme nazývat uspořádanou množinou sudého počtu celých čísel (a[2i], a[2i+1],..., kde i je očíslováno c 0), ve které každá dvojice čísel je a[2i], a[2i+1 ] určuje hranu grafu mezi vrcholy a[2i] a a[2i+1].
Tento záznamový formát neobsahuje informaci o tom, zda je graf orientovaný (možné jsou obě možnosti). Při použití formátu digraph je hrana považována za směrovanou z a[2i] do a[2i+1]. Zde a níže: u neorientovaných grafů lze v případě potřeby uplatnit požadavky na pořadí záznamů vrcholů (např. aby byl na prvním místě vrchol s nižší hodnotou čísla, které mu bylo přiděleno).
V C++ je vhodné zadat vektor sousednosti pomocí std::vector, odtud název této datové struktury.
Případ (a2): nevážený graf, váhy hran jsou celá čísla
Analogicky s případem (a1) nazýváme vektor sousednosti pro váž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 očíslováno c 0), kde každá „triplet“ čísel a[3i], a[3i+1], a[3i+2] určuje hranu grafu mezi vrcholy očíslovanými a[3i] a a[3i+1] a hodnota a [3i+2] je váha této hrany. Takový graf může být také směrovaný nebo ne.
Případ (b): nevážený graf, neceločíselné váhy hran
Protože je nemožné uložit heterogenní prvky do jednoho pole (vektoru), je například možná následující implementace. Graf je uložen ve dvojici vektorů, z nichž první vektor je vektor sousednosti grafu bez určení vah a druhý vektor obsahuje odpovídající váhy (možná implementace pro C++: std::pair ). Tedy pro hranu definovanou dvojicí vrcholů pod indexy 2i, 2i+1 prvního vektoru bude váha rovna prvku pod indexem i druhého vektoru.
Proč je to nutné?
No, autorovi těchto řádků se to docela hodilo pro řešení řady problémů. Z formálního hlediska to budou následující výhody:
- Vektor sousednosti, stejně jako jakákoli jiná „výčtová“ struktura, je poměrně kompaktní, zabírá méně paměti než matice sousedství (pro řídké grafy) a je relativně snadno implementovatelný.
- Vrcholy grafu lze v zásadě označit také zápornými čísly. Co když je taková „perverze“ potřeba?
- Grafy mohou obsahovat více hran a více smyček s různou váhou (kladná, záporná, dokonce nulová). Nejsou zde žádná omezení.
- Hranám můžete také přiřadit různé vlastnosti – ale více o tom viz část 4.
Je však třeba přiznat, že tento „seznam“ neznamená rychlý přístup k okraji. A zde přichází na pomoc Associative Adjacency Array, o čemž pojednáváme níže.
3.2 Asociativní přilehlé pole
Pokud je tedy pro nás přístup ke konkrétní hraně, její hmotnosti a dalším vlastnostem kritický a paměťové nároky nám neumožňují použít matici sousednosti, pak se zamysleme nad tím, jak bychom mohli změnit vektor sousednosti, abychom tento problém vyřešili. Klíčem je tedy hrana grafu, kterou lze zadat jako uspořádanou dvojici celých čísel. jak to vypadá? Není to klíč v asociativním poli? A pokud ano, proč to nezavedeme? Mějme asociativní pole, kde každý klíč - uspořádaný pár celých čísel - bude spojen s hodnotou - celým číslem nebo reálným číslem, které určuje váhu hrany. V C++ je vhodné implementovat tuto strukturu založenou na kontejneru std::map (std::map , int> nebo std::map , double>), nebo std::multimap, pokud se očekává více hran. No, máme strukturu pro ukládání grafů, která zabírá méně paměti než „maticové“ struktury, umí definovat grafy s více smyčkami a hranami a nemá ani striktní požadavky na nezápornost čísel vrcholů (nevím kdo to potřebuje, ale přesto).
4. Datové struktury jsou plné, ale něco chybí
A je to pravda: když řešíme řadu problémů, možná budeme muset okrajům grafu přiřadit nějaké charakteristiky a podle toho je uložit. Pokud je možné tyto vlastnosti jednoznačně redukovat na celá čísla, pak je možné ukládat takové „grafy s dalšími vlastnostmi“ pomocí rozšířených verzí vektoru sousednosti a asociativního pole sousednosti.
Mějme tedy nevážený graf, pro jehož každou hranu je potřeba uložit např. 2 další vlastnosti určené celými čísly. V tomto případě je možné definovat jeho vektor sousednosti 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] určí charakteristiky odpovídající hrany. U grafu s celočíselnými váhami hran je pořadí obecně podobné (jediný rozdíl bude v tom, že atributy budou následovat váhu hrany a budou určeny prvky a[2i+3] a a[2i+4] a samotná hrana nebude specifikována 4, ale 5 uspořádanými čísly). A pro graf s neceločíselnými váhami hran lze vlastnosti zapsat do jeho nevážené složky.
Při použití asociativního pole přilehlosti pro grafy s celočíselnými váhami hran je možné zadat jako hodnotu nikoli jedno číslo, ale pole (vektor) čísel, které kromě váhy hrany specifikují i všechny její další potřebné funkce. Nepříjemností pro případ neceločíselných vah bude zároveň nutnost specifikovat znaménko s číslem s plovoucí desetinnou čárkou (ano, je to nepříjemnost, ale pokud takových znamének není tolik a pokud nemáte Nenastavujte je příliš „ošidně“ dvakrát, pak to nemusí být nic) . To znamená, že v C++ lze pole rozšířené asociativní přilehlosti definovat takto: std::map , std::vector> nebo std::map , std::vector, ve kterém první hodnota v „klíč-hodnota-vektor“ bude váha hrany a dále jsou umístěna číselná označení jejích charakteristik.
Literatura:
O grafech a algoritmech obecně:
1. Cormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Algoritmy: konstrukce a analýza, 2. vydání: Trans. z angličtiny – M.: Williams Publishing House, 2011.
2. Harari Frank. Teorie grafů. M.: Mir, 1973.
Autorova zpráva o stejném vektorovém a asociativním poli sousedností:
3. Chernoukhov S.A. Vektorová a asociativní pole sousednosti jako způsoby reprezentace a ukládání grafů / SA Chernouhov. Vektor sousedství a mapa sousedství jako datové struktury k reprezentaci grafu // Sborník článků Mezinárodní vědecké a praktické konference „Problémy implementace výsledků inovativního vývoje a způsoby jejich řešení“ (Saratov, 14.09.2019. září 2019). – Sterlitamak: AMI, 65, str. 69-XNUMX
Užitečné online zdroje na toto téma:
4.
5.
Zdroj: www.habr.com