V kapitole [ref]chapter_grafy_a_stromy[/ref] jsme se dozvěděli, co to jsou grafy a k čemu jsou dobré. Brzo budeme chtít napsat nějaký program, který s grafy pracuje. Ale jak si takový graf uložit do počítače? To si teď vysvětlíme.

Všechny možné reprezentace si budeme vysvětlovat na následujícím grafu $G=(V,E)$ a orientovaném grafu ${H}=(W, {F})$. V každé sekci budou jejich reprezentace uvedeny jako příklad.



V této knize označujeme vrcholy grafu písmeny abecedy. Je to tak lepší pro výklad a diskuse nad grafy v příkladech. V počítači označujeme vrcholy pomocí čísel $1$, $2$ až $n$.1

Výhody a nevýhody jednotlivých reprezentací jsou shrnuty na konci kapitoly.

Seznam hran

Uložíme si počet vrcholů a seznam všech hran. Hrana je dvojice vrcholů. V neorientovaných grafech je jedno, jestli si hranu $uv\in E$ pamatujeme jako dvojici $uv$ nebo $vu$. Ale v případě orientovaných grafů už musíme dodržet správné pořadí vrcholů. Většinou za správné pořadí považujeme to po směru šipky. Orientovaný graf může kromě šipky $uv$ obsahovat i opačnou šipku $vu$.


Příklad: Neorientovaný graf na obrázku má $5$ vrcholů $A$ až $E$ a seznam hran $AB$, $AC$, $AD$, $BD$, $CD$, $DE$.

Orientovaný graf má $4$ vrcholy $a$ až $d$ a seznam hran $ab$, $ac$, $ba$, $cb$ a $dc$.

Tato reprezentace je vhodná spíše pro zadávání grafu na vstupu nebo pro skladování grafu na pevném disku.

Matice sousednosti,

Matice sousednosti zachycuje, které vrcholy spolu sousedí. V matici si pro každou dvojici vrcholů $(u,v)$ pamatujeme, jestli z vrcholu $u$ vede hrana do vrcholu $v$. Z toho je vidět, že matice reprezentuje orientované grafy.

Neorientovaný graf $G$ si můžeme reprezentovat tak, že ho nejprve převedeme na orientovaný graf $\vec{G}$ a ten teprve reprezentujeme pomocí matice sousednosti. Orientovaný graf $\vec{G}$ dostaneme z $G$ tak, že každou neorientovanou hranu $uv\in E$ nahradíme dvojicí šipek $uv$ a $vu$, jdoucích proti sobě.

Matice sousednosti $A$ má velikost $n \times n$ a je definována jako $A=(a_{u,v})$, kde $$a_{u,v} = \left\{\begin{array}{l r} 0 & \Longleftrightarrow uv \not\in E \\ 1 & \Longleftrightarrow uv \in E \end{array}\right.$$

Protože graf neobsahuje smyčky (hrany z $v$ do $v$), tak je $a_{v,v}=0$ pro každý vrchol $v\in V$. Podobně je vidět, že pro neorientované grafy dostaneme symetrickou matici.

Příklad:

$A(G) =
\begin{matrix}
\begin{matrix}
A & B & C & D & E \\
\end{matrix} & {} \\
\begin{pmatrix}
0 & 1 & 1 & 1 & 0 \\
1 & 0 & 0 & 1 & 0 \\
1 & 0 & 0 & 1 & 0 \\
1 & 1 & 1 & 0 & 1 \\
0 & 0 & 0 & 1 & 0 \\
\end{pmatrix}
&
\begin{matrix}
A\\
B\\
C\\
D\\
E
\end{matrix}
\end{matrix}
$
$A(H) =
\begin{matrix}
\begin{matrix}
a & b & c & d \\
\end{matrix} & {} \\
\begin{pmatrix}
0 & 1 & 1 & 0 \\
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
\end{pmatrix}
&
\begin{matrix}
a\\
b\\
c\\
d
\end{matrix}
\end{matrix}
$

Matici sousednosti budeme celkem často používat, protože se s ní jednoduše pracuje. Hlavně velmi rychle zjistíme, jestli je $uv$ hranou grafu.

Matice sousednosti obsahuje jen nuly nebo jedničky. Často si ale boolovskou matici rozšíříme na matici integerů, protože pak si v $a_{ij}$ můžeme pamatovat ohodnocení hrany $ij$. Pokud graf není úplný, tak musíme určit jednu hodnotu, která znamená, že hrana neexistuje (běžně se bere “počítačové $\infty$”, které pro integery je MAXINT; podobně pokud jsou všechna ohodnocení hran nezáporná, tak můžeme použít $-1$). Pokud si do $a_{ij}$ uložíme vzdálenost vrcholu $i$ od vrcholu $j$, tak dostaneme matici vzdáleností.

Seznam sousedů

Reprezentaci si vysvětlíme pro orientované grafy. Neorientovaný graf $G$ bychom si reprezentovali tak, že ho nejprve převedeme na orientovaný graf $\vec{G}$, který už budeme umět reprezentovat (viz jak to bylo popsáno u matice sousednosti).

Teď se podívejme, jak reprezentovat orientovaný graf $G=(V,E)$. Pro každý vrchol $v\in V$ si budeme pamatovat seznam jeho sousedů. To je vrcholy, do kterých z $v$ vede hrana.

Příklad:

Příklad:

Abychom se vyhnuli spojovým seznamům a přitom neplýtvali pamětí, tak jednotlivé seznamy poskládáme za sebe do jednoho pole. Abychom neztratili přehled o tom, kde který seznam sousedů začíná, tak si stále ponecháme pole $\ARRAY{V}{\cdot}$ obsahující ukazatele na začátky seznamů. Políčko $\ARRAY{V}{i}$ bude obsahovat index do pole $\ARRAY{Sousedi}{\cdot}$, na kterém začíná seznam sousedů vrcholu $i$. Seznam sousedů vrcholu $i$ bude končit o jednu pozici dříve než začíná seznam sousedů vrcholu $i+1$. Abychom věděli kde končí seznam sousedů posledního vrcholu, tak rozšíříme obě pole o jedna (odpovídá to přidání fiktivního vrcholu s prázdným seznamem sousedů).

Příklad:


Výhody a nevýhody jednotlivých reprezentací

Nejprve si musíme rozmyslet, co chceme v grafu dělat. Mezi nejčastější operace patří testování, jestli jsou dva vrcholy $u\in V$ a $v\in V$ spojeny hranou. Jinými slovy potřebujeme zjistit, zda je $uv$ hrana. Druhou častou operací je průchod všech sousedů vrcholu $v$.

Následující tabulka shrnuje, jak dlouho tyto dotazy trvají v jednotlivých reprezentacích. Zároveň udává i prostorovou složitost každé reprezentace.

Reprezentace Je $uv$ hrana? Projít sousedy $v$ Prostorová složitost
seznam hran $\OO(m)$ $\OO(m)$ $\OO(m)$
matice sousednosti $\OO(1)$ $\OO(n)$ $\OO(n^2)$
seznam sousedů $\OO(n)$ $\OO(\mbox{#sousedů})$ $\OO(n+m)$

Matice sousednosti nám jako jediná reprezentace umožňuje v konstantním čase určit, jestli je $uv$ hrana grafu (však je tomu šitá na míru). Pro řídké grafy (grafy, které mají málo hran) za to zaplatíme vyšší paměťovou náročností. Příkladem řídkých grafů jsou rovinné grafy, které mají nejvýše $3n-6 = \OO(n)$ hran. Na druhou stranu pro husté grafy (grafy, které mají alespoň $c\cdot n^2$ hran pro nějaké $c>0$) je to ideální reprezentace. Zabere lineárně mnoho prostoru ve velikosti grafu, testování, jestli je $uv$ hrana, proběhne v čase $\OO(1)$ a dokonce i průměrný počet sousedů je $\Omega(n)$.

V některých algoritmech hodně často procházíme všechny sousedy některých vrcholů a testy, zda je $uv$ hrana, ani nepotřebujeme. V takových případech je nejlepší použít reprezentaci grafu seznamem sousedů.

Z předchozích odstavců je vidět, že je každá reprezentace někdy výhodná, každá jindy. Záleží na tom, co s grafem chceme provádět. Pro každý algoritmus si musíme vybrat individuálně.


Poznámka: Někdy si spolu s grafem chceme reprezentovat i jeho další vlastnosti. Například pro rovinné grafy chceme znát seznam všech stěn. Pro každou stěnu chceme rychle zjistit seznam hran a vrcholů, které obsahuje. Naopak pro každou hranu chceme vědět, ve kterých stěnách je obsažena. Návrh takové datové struktury už není složitý a proto necháváme na čtenáři, aby si rozmyslel, jak takové věci efektivně reprezentovat.