# ADS: přednáška

- grafové algoritmy
- prohledávání do hloubky a do šířky
- graf G, BÚNO orientovaný
- reprezentace grafu
	- matice sousednosti – prostor $\Theta(n^2)$
	- seznamy sousedů – prostor $\Theta(n+m)$, kde $n$ je počet vrcholů, $m$ je počet hran

## Prohledávání do hloubky

- stav vrcholu – neviděný / otevřený / zavřený
- DFS(v):
	- stav(v) $\leftarrow$ otevřený
	- pro $vw\in E$:
		- pokud stav(w) == neviděný:
			- DFS(w)
	- stav(v) $\leftarrow$ zavřený
- inicializace: všechny vrcholy nastavíme jako neviděné
- lemma: Po doběhnutí DFS(u) je stav(v) buď neviděný, nebo zavřený. Stav(v) je zavřený $\iff\exists$ cesta z u do v.
- důkaz
	- pozorování: neviděný → otevřený → zavřený
	- $v$ otevřený nebo zavřený $\implies v$ dosažitelný
		- indukcí podle doby běhu
	- $v$ dosažitelný $\implies v$ na konci zavřený
		- důkaz sporem – minimálním protipříkladem
		- kdyby neplatilo, existuje „špatný vrchol“ $x$, který je dosažitelný, ale nenalezený
		- zvolíme $x$ takový, že cesta $u\to x$ má nejméně hran
		- určitě $u\neq x$
		- na cestě $u\to x$ zvolíme $p$, což je předposlední vrchol před vrcholem $u$
		- $p$ je určitě „dobrý“ (hledali jsme $x$ s nejméně hranami)
		- museli jsme vstoupit do $p\implies$ objevit hranu $px$, což je spor
- lemma: DFS běží v čase $\Theta(n+m)$
- důkaz
	- pozorování: do každého vrcholu vstoupíme maximálně jednou
	- dva přístupy
		- $\Theta(\sum_v\Theta(1+\text{deg}^{\text{out}}(v)))=\Theta(n+m)$
		- účtujeme vrcholům a hranám
- opakované DFS
	- $\forall v\in v:$ stav(v) $\leftarrow$ neviděn
	- pro všechna v:
		- je-li stav(v) == neviděn:
			- DFS(v)
- opakované DFS by mělo větší složitost – ale lze převést na přidání jednoho vrcholu a jeho připojení ke všem vrcholům grafu → asymptotika je zachována
- DFS strom
	- tvoří ho stromové hrany
	- zpětné hrany – vede do otevřeného vrcholu (do předka)
	- dopředné hrany – vede do zavřeného vrcholu, který je potomkem
	- příčné hrany – vede do zavřeného vrcholu, který není potomkem; vždy zprava doleva
- klasifikace hran
	- pro hranu xy může průchod vrcholy vypadat takto
		- $(_x\quad)_x\quad(_y\quad)_y$ – nenastane
		- $(_y\quad)_y\quad(_x\quad)_x$ – příčná
		- $(_x\quad(_y\quad)_y\quad)_x$ – stromová nebo dopředná
		- $(_y\quad(_x\quad)_x\quad)_y$ – zpětná
- hrana v neorientovaném grafu
	- když ji vidím poprvé → stromová, podruhé zpětná
	- poprvé zpětná, podruhé dopředná
- věta: DFS(u) běží v čase $\Theta(n+m)$ a prostoru $\Theta(n+m)$ a najde dosažitelné vrcholy a klasifikace hran mezi nimi.
- hledání mostů v neorientovaných grafech
	- df: $e$ je most $\equiv (G-e)$ má více komponent souvislosti než $G$
	- pozorování: $e$ není most $\iff e$ leží na kružnici
	- pozorování: zpětná hrana nemůže být most
	- stromová hrana xy není most $\iff\exists$ zpětná hrana ab, kde a leží ve stromu pod y, b leží ostře nad y
	- df: low(v) := min { in(b) } (???)
	- low(v) = min { low(s1), …, low(sk), in(b) | vb zpětné hrany } (???)
	- DFS algoritmus umí o každé hraně v neorientovaném grafu rozhodnout, jestli je to most