
\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 }}

\newcommand{\WHILE}{\texttt{\color{red}While }}
\newcommand{\Do}{\texttt{\color{red}Do }}
\newcommand{\FOR}{\texttt{\color{red}For }}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

{\small
\noindent
\textbf{\normalsize The Breadth-First Search (BFS) algorithm} \\
  \texttt{\color{red}Input.} A connected graph $G=(V,E)$ and vertex $v \in V$. \\
  \texttt{\color{red}Output.} A set $E_T$ of edge such that $(V,E_T)$ is a spanning tree of $G$.
  \begin{itemize}
  \item[1.] \Let $E_T=\emptyset$ and $Q$ be an empty queue.
  \item[2.] Insert $v$ in $Q$ and mark $v$ as visited.
  \item[3.] \WHILE $Q$ is not empty \Do
    \begin{itemize}
    \item[a)] \Let $v$ be the vertex at the front of the queue $Q$.
    \item[b)] Remove $v$ from $Q$.
    \item[c)] \FOR each unvisited neighbor $i$ of $v$ \Do \\
      \quad (i) Insert $i$ at the end of the queue $Q$ and mark $i$ as visited. \\
      \quad (ii) Add the edge $\{v,i\}$ to $E_T$.
    \end{itemize}
  \item[3.] \return the graph $(V,E_T)$
  \end{itemize}
}

\medskip
Example $v=1$.

\medskip
\quad \quad \includegraphics[height=3cm]{bfsdfs.png}
\quad Question: How can we test if $G$ is connected?


\medskip
