\algo
\:Zaèneme libovolným vrcholem $v_0$, $T\leftarrow \{v_0\}$.
\:Do~haldy $H$ umístíme v¹echny hrany vedoucí z~$v_0$.
-\:Opakuji dokud $H\neq\emptyset$:
+\:Opakujeme, dokud $H\neq\emptyset$:
\::$vw\leftarrow \<DeleteMin>(H)$, pøièem¾ $v\not\in T, w\in T$.
\::$T\leftarrow T\cup\{vw\}$
-\::Pro v¹echny sousedy $u$ vrcholu $v$, které dosud nejsou v~$T$, upravíme haldu:
+\::Pro v¹echny sousedy $u$ vrcholu $v$, kteøí dosud nejsou v~$T$, upravíme haldu:
\:::Pokud je¹tì v~$H$ není hrana incidentní s~$u$, pøidáme hranu~$uv$.
\:::Pokud u¾ tam nìjaká taková hrana je a je-li tì¾¹í ne¾ $uv$, nahradíme ji
hranou~$uv$ a provedeme \<DecreaseKey>.
\endalgo
\s{Pozorování:}
-Pokud algoritmus je¹tì neskonèil, je ka¾dá z~nalezených podkoster v~$T$ incidentní s~alespoò $k$ hranami.
+Pokud algoritmus je¹tì neskonèil, je ka¾dá z~nalezených podkoster v~$T$ incidentní s~alespoò $k$ hranami
+(do toho poèítáme i vnitøní hrany vedoucí mezi vrcholy podkostry).
Jak to vypadá pro jednotlivá ukonèení:
\numlist\ndotted
\itemcount=\algcnt
\:$\O(m)$ pro grafy s~celoèíselnými vahami (na~RAMu) \cite{fw90trans} -- uká¾eme v~jedné
z~následujících kapitol.
\:$\O(m)$, pokud u¾ máme hrany setøídìné podle vah: jeliko¾ víme, ¾e zále¾í jen na~uspoøádání,
- mù¾eme váhy pøeèíslovat na~$1\ldots n$ a pou¾ít pøedchozí algoritmus.
+ mù¾eme váhy pøeèíslovat na~$1\ldots m$ a pou¾ít pøedchozí algoritmus.
\:$\O(m)$ randomizovanì v~prùmìrném pøípadì \cite{karger:randomized}.
\:Na~zji¹tìní, zda je zadaná kostra minimální, staèí $\O(m)$ porovnání \cite{komlos:verify} a dokonce
lze v~lineárním èase zjistit, která to jsou \cite{king:verify}. Z~toho ostatnì vychází pøedchozí