Nastavení

Předpokládejme, že G je orientovaný graf a předpokládejme, že na počátku v kroku (7) existuje aspoň jeden zdroj $z$ a že všechny zdroje zařadíme do fronty $Q$.

\begin{algorithm}
\begin{algorithmic}
\STATE Vlož do $Q$ všechny vrcholy z s $\delta[z] = 0$\end{algorithmic}
\end{algorithm}

Vnitřek cyklu (8)-(17) realizuje odebrání 1 zdroje z fronty Q, jeho vyjmutí z grafu G, jeho vložení do výsledného uspořádání a identifikaci případných nových zdrojů a jejich zařazení do Q.

\begin{algorithm}
\begin{algorithmic}
\WHILE { $Q$ není prázdná }
    \STATE Odeber prvek $z$ ze začátku fronty $Q$
    \STATE Vypiš $z$
    \FOR { každou hranu $(z, w)$ vedoucí ze $z$ }
        \STATE $\delta[w]−−$
        \IF { Pokud $\delta[w] = 0$ }
            \STATE zařaď $w$ do $Q$ 
        \ENDIF
    \ENDFOR
\ENDWHILE\end{algorithmic}
\end{algorithm}

Existence hrany $(v_i , v_j)$ znemožňuje vložit vrchol $v_j$ do fronty $Q$ před vrcholem $v_i$, protože $v_j$ by v takovém okamžiku mělo $\delta[v_j] \gt 1$ a podmínkou vložení do $Q$ je $\delta[v_j] = 0$.

Pokud v okamžiku vyprázdnění fronty jsou zpracovány všechny vrcholy grafu $G$, našli jsme TU orientovaného acyklického grafu.

Pokud je fronta prázdná a přesto zbývají nějaké nezpracované vrcholy ve zbytku $G$, pak ve zbytku $G$ nejsou žádné zdroje, čili každý vrchol má vstupní hranu/-y a musí existovat orientovaný cyklus, plus případně z něj dostupné podgrafy. Vrcholy tohoto zbytkového grafu nelze topologicky uspořádat

Algoritmus tedy správně detekuje existenci cyklu a skončí v konečném čase

V obou případech algoritmus pracuje korektně a zastaví se

$\square$

Výpočet pole vstupních stupňů na řádcích (4)-(5) trvá $\Theta(|E|)$.

\begin{algorithm}
\begin{algorithmic}
\FOR { každou hranu $(u, v) \in E(G)$ }
    \STATE $\delta[v] + +$
\ENDFOR\end{algorithmic}
\end{algorithm}

Počáteční vložení zdrojů do $Q$ na řádku (7) trvá $O(|V|)$.

\begin{algorithm}
\begin{algorithmic}
\STATE Vlož do $Q$ všechny vrcholy z s $\delta[z] = 0$\end{algorithmic}
\end{algorithm}

Každý vrchol je vložen do $Q$ nejvýše 1x, proto vybírání z $Q$ a výpis na výstup na řádcích (9)–(10) trvá $O(|V|)$.

\begin{algorithm}
\begin{algorithmic}
\STATE Odeber prvek $z$ ze začátku fronty $Q$
\STATE Vypiš $z$\end{algorithmic}
\end{algorithm}

Každá hrana může být odebrána z grafu nejvýše 1x, proto operace na řádcích (11)–(16) trvají $O(|E|)$.

\begin{algorithm}
\begin{algorithmic}
\FOR { každou hranu $(z, w)$ vedoucí ze $z$ }
    \STATE $\delta[w]−−$
    \IF { Pokud $\delta[w] = 0$ }
        \STATE zařaď $w$ do $Q$ 
    \ENDIF
\ENDFOR\end{algorithmic}
\end{algorithm}

Celková časová složitost je tedy $O(|V| + |E|)$.

Graf $G$, pole $\delta[]$, fronta $Q$, to vše zabere $O(|V| + |E|)$ paměti.

$\square$