From f74728dc087777769ac7b1a8a729e4ce491a2c26 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Tue, 24 May 2011 18:21:01 +0200 Subject: [PATCH] Kostry: Odstraneni slimejsu --- 7-kostry/7-kostry.tex | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-) diff --git a/7-kostry/7-kostry.tex b/7-kostry/7-kostry.tex index bec8b0d..505c81f 100644 --- a/7-kostry/7-kostry.tex +++ b/7-kostry/7-kostry.tex @@ -68,11 +68,12 @@ jednozna \s{Implementace:} \itemize\ibull \:Pøímoèará: pamatujeme si, které vrcholy a hrany jsou v kostøe $T$ a které ne. Èasová slo¾itost je $\O(nm)$. -\:Chytøej¹í: Pro $v\notin V(T)$ si pamatujeme $D(v)=\min\left\{w(uv):u\in T\right\}$. Pøi ka¾dém +\:Chytøej¹í: Pro ka¾dý vrchol $v\notin V(T)$ si pamatujeme $$D(v)=\min\left\{w(uv):u\in T\right\},$$ +tedy nejlehèí hranu, která vede mezi~$T$ a~$v$. Pøi ka¾dém prùchodu hlavním cyklem pak procházíme v¹echna~$D(v)$ (to v¾dy trvá $\O(n)$) a pøi pøidání vrcholu do~$T$ kontrolujeme okolní~$D(w)$ pro $vw\in E$ a pøípadnì je sni¾ujeme (za~ka¾dou hranu~$\O(1)$). Èasovou slo¾itost tím celkovì zlep¹íme na~$\O(n^2+m)=\O(n^2)$. -\:S pou¾itím haldy: $D(v)$ ukládáme do haldy. Potom provedeme nanejvý¹ $n$-krát {\I ExtractMin}, nanejvý¹ $n$-krát {\I Insert} a nanejvý¹ $m$-krát {\I Decrease}. Pro binární haldu to má èasovou slo¾itost $\O(m \log n)$. V¹imnìte si, ¾e Jarníkùv algoritmus s $D(v)$ je velmi podobný Dijkstrovu algoritmu pro nejkrat¹í cesty. Rozbor slo¾itosti pro rùzné typy hald proto také dopadne stejnì. +\:S pou¾itím haldy: $D(v)$ ukládáme do haldy. Potom provedeme nanejvý¹ $n$-krát {\I ExtractMin}, nanejvý¹ $n$-krát {\I Insert} a nanejvý¹ $m$-krát {\I Decrease}. Pro binární haldu to má èasovou slo¾itost $\O(m \log n)$. V¹imnìte si, ¾e Jarníkùv algoritmus s $D(v)$ je velmi podobný Dijk\-stro\-vu algoritmu pro nejkrat¹í cesty. Rozbor slo¾itosti pro rùzné typy hald proto také dopadne stejnì. \endlist \h{Borùvkùv algoritmus} -- 2.39.2