5.2 DFS

Definice 5.3 (Prohledávání do hloubky / Depth-first search)

Buď neorientovaný graf $G = (V,E)$ a startovní vrchol $s \in V$ vstupem DFS

Poznámka 5.1

V přednáškách žádná definice není uvedená

\begin{algorithm}
\begin{algorithmic}
\FUNCTION { DFSgraf }{ graf $G$, vrchol $s$ }
    \FOR {každý vrchol $u \in V(G)$}
        \STATE stav[u] := nenalezený
    \ENDFOR
    \STATE \CALL{DFS}{s}
\ENDFUNCTION
\STATE
\FUNCTION {DFS}{vrchol $v$}
    \IF {stav[v] je otevřený nebo uzavřený}
        \RETURN
    \ENDIF
    \STATE stav[v] := otevřený
    \FOR {každého souseda u vrcholu v}
        \STATE \CALL{DFS}{u}
    \ENDFOR
    \STATE stav[v] := uzavřený 
\ENDFUNCTION\end{algorithmic}
\end{algorithm}

Algoritmus 5.2: Algoritmus DFS (graf G, vrchol s)