256 lines
9.6 KiB
Markdown
256 lines
9.6 KiB
Markdown
# Graf
|
||
|
||
- podchycuje obecný vztah (relaci) mezi prvky
|
||
- strom je speciální typ grafu
|
||
|
||
### Druhy grafů
|
||
|
||
- **Orientovaný graf**
|
||
- podchycuje nesymetrické vztahy
|
||
|
||
### Formální definice
|
||
|
||
- **Neorientovaný graf** $G$ je dvojice $V, E$:
|
||
- $V$ je množina vrcholů (vertex, vertices)
|
||
- $E$ je množina hran (edges)
|
||
- Hrana je dvouprvková množina $\{ a,b \}, a \in V, b \in V$ (nezáleží na pořadí)
|
||
- **Orientovaný graf** $G$ je dvojice $V, E$:
|
||
- $V$ je množina vrcholů (vertex, vertices)
|
||
- $E$ je množina hran (edges)
|
||
- Hrana je uspořádaná dvojice prvků $( a,b ), a \in V, b \in V$ (záleží na pořadí)
|
||
- mají šipku
|
||
|
||
**Značení**
|
||
- $\vert V\vert$ - počet vrcholů grafu
|
||
- $\vert E\vert$ - počet hran grafu
|
||
+ $V(G)$ - množina vrcholů grafu $G$
|
||
+ $E(G)$ - množina hran grafu $G$
|
||
- $y \in V$ je sousedem $x \in V$ právě když
|
||
- existuje orientovaná hrana $E = (x, y)$
|
||
- existuje neorientovaná hrana $E, x \in E, y \in E$
|
||
|
||
### Operace
|
||
|
||
- vytvoření grafu s danou množinou vrcholů $V$ (bez hran)
|
||
- přidání (ne)orientované hrany
|
||
- zjištění všech sousedů vrcholu $x \in V$
|
||
- zjištění, zda je $y \in V$ sousedem $x \in V$ (test sousednosti)
|
||
|
||
### Vrchol
|
||
|
||
- můžou s ním být asiciována data
|
||
- ADT Graf **neumožňuje** odebírat a přidávat vrcholy
|
||
- data vrcholů je možné **držet mimo ADT v poli**
|
||
- jedinou reprezentací vrcholu je jeho **index**
|
||
|
||
### Implementace
|
||
|
||
- seznamy sousednosti
|
||
- matice sousednosti
|
||
+ implementace se liší pro orientované a neorientované grafy
|
||
|
||
#### Implementace seznamem sousednosti
|
||
|
||
- každý vrchol má své sousedy uložené v ADT Seznam
|
||
- není vhodné použít např. `LinkedList`
|
||
- nevyužijeme většinu funkcionality
|
||
- program by byl neefektivní (konverze `int`/`Integer`)
|
||
- chceme vědět, jak věci fungují uvnitř
|
||
- použijeme vlastní implementaci se spojovacím prvkem
|
||
- typ dat: `int`
|
||
+ reference na první prvek každého seznamu jsou uloženy v poli velikosti $\vert V\vert$
|
||
|
||
**Operace**
|
||
- přidání hrany
|
||
- pro neorientovaný přidáme obě hrany (z **A** do **B** a zároveň z **B** do **A**)
|
||
- vkládáme na **začátek**, je to **rychlejší**
|
||
- nalezení sousedů
|
||
- projdeme náš seznam `edges`
|
||
- **složitost**
|
||
- záleží na počtu sousedů
|
||
- husté grafy: počet sousedů může být $\Omega(\vert V\vert)$
|
||
- řídké grafy: průměrný počet sousedů $\mathcal{O}(1)$
|
||
- test sousednosti
|
||
- projdeme všechny sousedy a porovnáváme s hledaným
|
||
- složitost jako u hledání sousedů
|
||
|
||
**Úprava na ohodnocený graf**
|
||
- na každé hraně má přiřazené číslo (např. délka cesty, propustnost, ...)
|
||
- do spojovacího prvku přidáme ohodnocení hrany
|
||
|
||
#### Implementace maticí sousednosti
|
||
|
||
**Orientovaný graf**
|
||
- Matice $\vert V\vert \times \vert V\vert$ obsahuje na pozici $[i, j]$
|
||
- **1**, pokud z $i$-tého vrcholu vede hrana do $j$-tého
|
||
- **0**, pokud ne
|
||
|
||
**Neorientovaný graf**
|
||
- Matice $\vert V\vert \times \vert V\vert$ obsahuje na pozici $[i, j]$ a $[j, i]$
|
||
- **1**, pokud z $i$-tého vrcholu vede hrana do $j$-tého
|
||
- **0**, pokud ne
|
||
|
||
**Reprezentace matice**
|
||
- `int[][]` - alokováno zbytečně moc paměti
|
||
- `byte[][]` - bude nám stačit
|
||
- `boolean[][]` - překladač i pro `boolean` alokuje celý `byte`
|
||
+ první index - **řádek**
|
||
+ druhý index - **sloupce**
|
||
|
||
**Operace**
|
||
- přidání hrany
|
||
- nastavíme 1 na [i, j] (u neorientovaného grafu na [i, j] i [j, i])
|
||
- nalezení sousedů vrcholu `v`
|
||
- projdeme celou řádku - `matrix[v][i]`
|
||
- složitost $\Theta(\vert V\vert)$ nezávisle na hustotě grafu
|
||
- test sousednosti
|
||
- zjištění, jestli na [i, j] je 1
|
||
- složitost $\mathcal{O}(1)$ nezávisle na hustotě grafu
|
||
|
||
**Úprava na ohodnocený graf**
|
||
- matice jako `double[][]`
|
||
- v matici na pozici [i, j] uložíme ohodnocení hrany
|
||
- na ostatních pozicích bude hodnota mimo rozsah ohodnocení
|
||
- `-1`, pokud ohodnocení nesmí být záporné
|
||
- `NaN`, pokud `NaN` není přípustným ohodnocením
|
||
- záleží na konkrétní aplikaci
|
||
|
||
#### Porovnání implementací
|
||
|
||
**Paměťová složitost**
|
||
- seznam: $\mathcal{O}(\vert V\vert + \vert E\vert)$
|
||
- matice: $\Omega(\vert V\vert^2)$
|
||
|
||
**Výpočetní složitost operací**
|
||
- vložení hrany
|
||
- seznam i matice: $\mathcal{O}(1)$
|
||
- nalezení sousedů vrcholu
|
||
- seznam: $\Omega(n)$, $n$ je počet sousedů vrcholu
|
||
- matice: $\Omega(\vert V\vert)$
|
||
- test sousednosti
|
||
- seznam: $\Omega(n)$, $n$ je počet sousedů vrcholu
|
||
- matice: $\mathcal{O}(1)$
|
||
|
||
**Záleží na hustotě grafu**
|
||
- Řídký graf
|
||
- $\vert E\vert \ll \vert V\vert^2$
|
||
- obvykle vhodnější implementace seznamem sousedů
|
||
- např. pro planární trojúhelníkové sítě se dá dokázat, že průměrný počet vrcholů je blízký 6
|
||
- složitost testu sousednosti v průměru $\mathcal{O}(1)$
|
||
- Hustý graf
|
||
- $\vert E\vert \simeq \vert V\vert^2$, případně $\vert E\vert = k\vert V\vert^2$ pro nějakou konstantu $k$
|
||
- obvykle vhodnější implementace maticí sousedů
|
||
|
||
### Procházení grafu
|
||
|
||
**Příklady**
|
||
- Existuje v grafu cesta z vrcholu A do B?
|
||
- **Graf**: bludiště
|
||
- **Vrchol**: křižovatka
|
||
- **Hrana**: cesta mazi křižovatkami
|
||
- **Úkol**: zjistit, zda existuje cesta z jednoho místa na jiné
|
||
+ Jak dlouhá (kolik hran) je nejkratší cesta z vrcholu A do vrcholu B?
|
||
+ **Graf**: vlaková spojení
|
||
+ **Vrchol**: nádraží
|
||
+ **Hrana**: mezi nádražími jede přímý spoj
|
||
+ **Úkol**: vyhledat spojení s nejmenším počtem přestupů
|
||
- Které vrcholy se v grafu vyskytují ve vzdálenosti menší než $k$ (počet hran)?
|
||
- **Graf**: síť kontaktů LinkedIn
|
||
- **Vrchol**: záznam osoby
|
||
- **Hrana**: konexe
|
||
- **Úkol**: prohledat konexe do úrovně $k$, zda obsahují hledanou osobu
|
||
+ Existuje v orientovaném grafu cyklus?
|
||
+ **Graf**: vztah buněk v tabulkovém kalkulátoru
|
||
+ **Vrchol**: buňka
|
||
+ **Hrana** $A \to B$: hodnota buňky $A$ zavísí na hodnotě buňky $B$
|
||
+ **Úkol**: zjistit, zda je možné tabulku vyhodnotit (nesmí obsahovat cyklus!)
|
||
- Přiřadit vrcholům indexy tak, že hrany vedou vždy od menšího indexu k většímu
|
||
- **Graf**: závislosti činností
|
||
- **Vrchol**: činnost
|
||
- **Hrana** $A \to B$: činnost $B$ může být vykonána, teprve když je činnost $A$ hotová
|
||
- **Úkol**: zjistit, v jakém pořadí je možné činnosti vykonat
|
||
|
||
#### Prohledávání do šířky (BFS)
|
||
|
||
- Breadth-First Search
|
||
+ zpracovává vrcholy grafu od vrcholu `s` v pořadí **od blízkých ke vzdáleným**
|
||
+ postup vyžaduje označování vrcholů
|
||
+ označení uložíme do pole délky $\vert V\vert$
|
||
+ vrcholy se vkládají do fronty
|
||
+ všechny vrcholy ve vzdálenosti `k` se zpracují před těmi se vzdáleností `> k`
|
||
|
||
**Značení vrcholů**
|
||
+ nenavštívený (kód 0)
|
||
+ čekající na zpracování (kód 1)
|
||
+ hotový (kód 2)
|
||
|
||
**Pozorování**
|
||
- BFS je potřeba doplnit o nějaký užitečný kód
|
||
+ záleží to na řešeném problému
|
||
- BFS vždy zpracuje jen jednu komponentu (jen vrcholy dosažitelné ze startovního vrcholu)
|
||
- může se vyřešit pomocí metody `BFS_all`, která bude procházet `for`-cyklem všechny nezpracované vrcholy (kód 0)
|
||
|
||
**Složitost**
|
||
- vkládání do fronty
|
||
- každý vrchol jen jednou
|
||
- $\Omega(\vert V\vert)$
|
||
- procházení sousedů
|
||
- implementace grafu seznamem: $\mathcal{O}(\vert E\vert)$
|
||
- implementace grafu maticí: $\Omega(\vert V\vert^2)$
|
||
+ celkem
|
||
+ úplný, popř. hustý graf nebo implementace sousednosti maticí: $\Omega(\vert V\vert^2)$
|
||
+ implementace sousednosti seznamem: $\mathcal{O}(\vert V\vert + \vert E\vert)$
|
||
+ graf může mít počet hran až $\vert V\vert^2$
|
||
|
||
**Strom dosažitelnosti**
|
||
- tvoří se z nějakého určeného vrcholu (kořen)
|
||
- ukazuje, jaká je nejkratší cesta do ostatních vrcholů
|
||
- reprezentován polem, kde na indexu vrcholu je uložen předek
|
||
- nemusí být jednoznačný (může existovat více nejkratších cest)
|
||
|
||
#### Prohledávánı́ do hloubky (DFS)
|
||
|
||
- Depth-First Search
|
||
- algoritmus postupuje do většı́ vzdálenosti od počátečnı́ho vrcholu, pokud může
|
||
+ předpokládáme, že označenı́ (mark) je před volánı́m DFS inicializováno na 0 pro všechny vrcholy
|
||
+ DFS je potřeba doplnit o nějaký užitečný kód
|
||
+ záleží to na řešeném problému
|
||
|
||
**Značenı́ vrcholů**
|
||
- nezpracovaný (”bı́lá”), kód 0
|
||
- rozpracovaný (”šedá”), kód 1
|
||
- dokončený (”černá”), kód 2
|
||
|
||
**Složitost**
|
||
- rekurzivní metoda se pro každý vrchol volá pouze jednou - $\Omega(\vert V\vert)$
|
||
- pro každý vrchol se prochází seznam hran:
|
||
- reprezentace maticí - $\Omega(\vert V\vert^2)$
|
||
- reprezentace seznamem - $\mathcal{O}(\vert E\vert)$
|
||
- celkem: $\mathcal{O}(\vert V\vert + \vert E\vert)$ při reprezentaci seznamem
|
||
- může být i $\Omega(\vert V\vert^2)$, pokud $\vert E\vert = k\vert V\vert^2$
|
||
|
||
**Použití DFS**
|
||
- Zjištění dosažitelnosti vrcholu
|
||
- pokud předpokládáme, že bude vrchol daleko, je DFS vhodnější než BFS
|
||
+ Zjištění cyklu v grafu
|
||
+ vrchol označíme jedničkou a poté ho znovu hledáme
|
||
+ Topologické řazení
|
||
+ prvně je potřeba ověřit, že graf nemá cykly
|
||
+ vrcholy jsou činnosti, hrany jsou závislosti
|
||
+ hrana $A \to B$ značí, že se prvně musí vykonat A a potom až B
|
||
+ pomocí DFS můžeme snadno určit pořadí činností (pomocí otočeného grafu)
|
||
|
||
**DFS bez rekurze**
|
||
- pravděpodobně nastanou problémy s hloubkou zásobníku
|
||
+ vystačíme si se zásobníkem celých čísel (vrcholů)
|
||
+ `segment` (jaký je stav vrcholu) je v označení vrcholu (`mark`)
|
||
|
||
**Nejkratší cesta v ohodnoceném grafu**
|
||
- velmi častý problém
|
||
- ohodnocení: čas, vzdálenost, ...
|
||
- úkol: nalézt nejkratší vzdálenost ke všem vrcholům
|
||
- **Dijkstrův algoritmus**
|
||
- je potřeba prioritní fronta
|
||
- přidání dvojice vrchol + ohodnocení
|
||
- vybrání/odebrání vrcholu s nejmenším ohodnocením
|
||
- změna ohodnocení vrcholu |