

\newcommand{\Input}{\texttt{\color{red}Input }}
\newcommand{\Output}{\texttt{\color{red}Output }}
\newcommand{\Let}{\texttt{\color{red}Let }}
\newcommand{\IF}{\texttt{\color{red}If }}
\newcommand{\goto}{\texttt{\color{red}Goto }}
\newcommand{\return}{\texttt{\color{red}Return }}
\newcommand{\then}{\texttt{\color{red}Then }}
\newcommand{\ELSE}{\texttt{\color{red}Else }}
{\small

\textbf{The Depth-First Search (DFS) algorithm }

\texttt{\color{red}Input.} A graph $G=(V,E)$.

\texttt{\color{red}Output.} A set $E_T$ of edges such that $(V,E_T)$ is a spanning tree of $G$.

\begin{itemize}
\item[1.] \Let $v=1$, $E_T=\phi$ and and mark vertex $1$ as visited.
\item[2.] \IF all neighbors of $v$ have been visited \then
  \begin{itemize}
  \item[a)] \IF $v=1$ \then \return $E_T$.
  \item[b)] \ELSE ({\em backtrack step}) \Let $v=parent(v)$ and \goto step $2$.
% v = parent(v) not v = parent(i)
  \end{itemize}
\item[3.] \ELSE 
  \begin{itemize}
  \item[a)] \Let $i$ be the smallest neighbor of $v$ that has not been visited.
  \item[b)] Mark $i$ as visited.
  \item[c)] Add the edge $\{v,i\}$ to $E_T$ and \Let $parent(i)=v$.
  \item[d)] \Let $v = i$ and \goto step $2$.
  \end{itemize}
\end{itemize}
}

\medskip
Example

\medskip
\quad \quad \includegraphics[height=3cm]{bfsdfs.png} 
\medskip

% If we execute the DFS algorithm on the graph
% V={1,2,3,4,5,6}, {{4,5},{5,6},{1,2},{1,3},{2,3}}   V,{{1,2},{2,3}}
% what graph will it output?
% If we execute the DFS algorithm on the graph
% V={1,2,3,4,5,6}, {{1,2},{1,3},{1,4},{2,3},{2,4}}   V,{{1,2},{2,3},2,4}}
% what graph will it output?
