How to reproduce some attractive pseudo-code

You could try something entirely different.

article (report, or book) document classes

\documentclass{article}

\usepackage{minted}
\usepackage[many]{tcolorbox}
\tcbuselibrary{skins}
\tcbset{
    arc=0pt,
    outer arc=0pt,
    colback=white,
}

\definecolor{code-yellow}{RGB}{232, 168, 24}
\definecolor{code-blue}{RGB}{0, 114, 178}
\definecolor{code-green}{RGB}{0, 158, 115}

\begin{document}

\begin{tcolorbox}[text width=5cm]
\begin{minted}[escapeinside=||,mathescape=true]{text}
|\textsc{Traverse}|(|\color{code-blue}{$s$}|)

put |\color{code-blue}{$s$}| into the |\textcolor{code-yellow}{bag}|
while the |\textcolor{code-yellow}{bag}| is not empty
  take |$\color{code-blue}u$| from the |\textcolor{code-yellow}{bag}|
  if |\color{code-blue}{$u$}| unmarked
    |\textcolor{code-green}{mark}| |$\color{code-blue}u$|
    for every edge |$\color{code-blue}(u,v)$|
        put |$\color{code-blue}v$| into the |\textcolor{code-yellow}{bag}|
\end{minted}
\end{tcolorbox}

\end{document}

beamer document class

\documentclass{beamer}

\usepackage{minted}
\usepackage[many]{tcolorbox}
\tcbuselibrary{skins}
\tcbset{
    arc=0pt,
    outer arc=0pt,
    colback=white,
}

\definecolor{code-yellow}{RGB}{232, 168, 24}
\definecolor{code-blue}{RGB}{0, 114, 178}
\definecolor{code-green}{RGB}{0, 158, 115}

\begin{document}

\begin{frame}[fragile]

\begin{tcolorbox}[text width=5.5cm]
\begin{minted}[escapeinside=||,mathescape=true]{text}
|\textsc{Traverse}|(|\color{code-blue}{$s$}|)

put |\color{code-blue}{$s$}| into the |\textcolor{code-yellow}{bag}|
while the |\textcolor{code-yellow}{bag}| is not empty
  take |$\color{code-blue}u$| from the |\textcolor{code-yellow}{bag}|
  if |\color{code-blue}{$u$}| unmarked
    |\textcolor{code-green}{mark}| |$\color{code-blue}u$|
    for every edge |$\color{code-blue}(u,v)$|
        put |$\color{code-blue}v$| into the |\textcolor{code-yellow}{bag}|
\end{minted}
\end{tcolorbox}

\end{frame}

\end{document}

You can use semiverbatim, that's built in beamer.

\documentclass{beamer}
\usetheme{default}
\usepackage[framemethod=TikZ]{mdframed}

\title{Beamer Template}

\newcommand{\Proc}[1]{\textsc{#1}}
\newcommand{\Var}[1]{\ensuremath{\textcolor{varcolor}{#1}}}
\newcommand{\Tag}[1]{\textcolor{tagcolor}{#1}}
\newcommand{\Com}[1]{\textcolor{comcolor}{#1}}

\definecolor{varcolor}{RGB}{15,122,183}
\definecolor{tagcolor}{RGB}{230,159,3}
\definecolor{comcolor}{RGB}{10,161,119}

\begin{document}

\begin{frame}[fragile]

\begin{mdframed}
\begin{semiverbatim}
\Proc{Traverse}(\Var{s})

put \Var{s} into the \Tag{bag} 
while the \Tag{bag} is not empty
  take \Var{u} from the bag
  if \Var{u} unmarked
    \Com{mark} \Var{u}
    for every edge \Var{(u,v)}
      put \Var{v} into the \Tag{bag}    
\end{semiverbatim}
\end{mdframed}

\end{frame}

\end{document}

Don't forget the fragile option.

An alternative is to use BVerbatim from fancyvrb.

\documentclass{beamer}
\usetheme{default}
\usepackage{fancyvrb}

\title{Beamer Template}

\newcommand{\Proc}[1]{\textsc{#1}}
\newcommand{\Var}[1]{\ensuremath{\textcolor{varcolor}{#1}}}
\newcommand{\Tag}[1]{\textcolor{tagcolor}{#1}}
\newcommand{\Com}[1]{\textcolor{comcolor}{#1}}

\definecolor{varcolor}{RGB}{15,122,183}
\definecolor{tagcolor}{RGB}{230,159,3}
\definecolor{comcolor}{RGB}{10,161,119}

\newenvironment{pseudocode}
 {%
  \VerbatimEnvironment
  \begin{lrbox}{\pseudocodebox}
  \fvset{commandchars=\\\{\}}
  \begin{BVerbatim}
 }
 {\end{BVerbatim}\end{lrbox}\fbox{\usebox{\pseudocodebox}}}
\newsavebox{\pseudocodebox}

\begin{document}

\begin{frame}[fragile]

\begin{pseudocode}
\Proc{Traverse}(\Var{s})

put \Var{s} into the \Tag{bag} 
while the \Tag{bag} is not empty
  take \Var{u} from the bag
  if \Var{u} unmarked
    \Com{mark} \Var{u}
    for every edge \Var{(u,v)}
      put \Var{v} into the \Tag{bag}    
\end{pseudocode}

\end{frame}

\end{document}

As far as I know, mdframed always uses the whole text width. Check with tcolorbox for more powerful methods.