 
\documentclass{beamer}
\usepackage[utf8]{inputenc}
 
 
    
\usetheme{CambridgeUS}
 

\usepackage[francais]{babel}
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amssymb,amsfonts}
\usepackage[tikz]{bclogo}
\usepackage{listings}
 \usepackage{hyperref}

 \usetikzlibrary{arrows}


\newcommand\logopython {\includegraphics[width =17 pt]{logos/python-logo}}
\newenvironment{codepython}{%
\begin{bclogo}[logo = \logopython, noborder = true]{Python}%
}
{%
\end{bclogo}
}


\newcommand{\hp}{\hspace{1.2em}}
  \newcommand{\hpp}{\hspace{2.2em}}



 \newcommand{\hh}{\hspace{.6em}}
  \newcommand{\ha}{\hspace{2em}}
 \let\ds=\displaystyle

\title[Algorithmique]{Parcours d'un graphe}



\date{ISN 2013}
 
 
 


\lstdefinelanguage{pseudo}{
morekeywords={Entr\'ee, Sortie, Algorithme, Variables, locales, Corps,
  tant, que, si, alors, faire, renvoyer, pour, jusque, de} ,
sensitive ,%
morecomment=[l]\#,%
morecomment=[l]//,%
morecomment=[s]{/*}{*/},%
morestring=[b]",%
%morestring=[b]'%
}[keywords,comments,strings]

 
 
 % package tikz pour dessins
\usepackage{tikz}
\usetikzlibrary{shapes.geometric}
\usetikzlibrary{petri}
\usetikzlibrary{decorations}


 
\usepackage{verbatim}
%\let\resolution=\comment
%\let\endresolution=\endcomment

 \newenvironment{resolution}{ }{ }


\begin{document}

 \frame{\titlepage}


   


    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
%%%%%%%%%%%%%%  PARCOURS EN Profondeur
 
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
 \frametitle{Parcours de graphe}
 
 \hspace{3cm}  {\Large{Parcours en profondeur}}
\end{frame}




     \begin{frame}
   \frametitle{Parcours en profondeur : principe de l'algorithme }
   
   Vous devez parcourir toutes les pages d'un site web. Les pages sont les sommets d'un graphe et un lien entre deux pages est une arête entre ces deux sommets.  
  
  \begin{enumerate}
   \item<2-> Dans le parcours en profondeur, on utilise une pile. On empile le sommet de départ (on visite la page index du site).
   \item<3-> Si le sommet de la pile présente des voisins qui ne sont pas dans la pile, ni déjà passés dans la pile :
   \begin{itemize}
    \item<4-> alors on sélectionne l'un de ces voisins et on l'empile (en le marquant de son numéro de découverte),
    \item<5-> sinon on dépile (c'est à dire on supprime l'élément du sommet de la pile).
   \end{itemize}
   \item<6-> On recommence au point 2 (tant que la pile n'est pas vide).
  \end{enumerate}
\only<7>{En d'autres termes, on traite  toujours en priorité les  liens des pages les plus tard découvertes.  }
 
        
    \end{frame}
    
    
    
  \begin{frame}
   \frametitle{Parcours en profondeur d'un arbre}
   Parcourir en profondeur le graphe ci-dessous à partir du sommet s :
   
    \hspace{2cm}\scalebox{0.5}{
   \begin{tikzpicture}[every node/.style={circle,draw},
level 1/.style={sibling distance=5cm,level distance=4cm},
level 2/.style={sibling distance=2cm,level distance=4cm},
level 3/.style={sibling distance=2cm,level distance=4cm}]
  \node{\textcolor{red}{s}}
child{node{\textcolor{white}{2}}child{node{\textcolor{white}{3 }}}child{node{\textcolor{white}{4}}child{node{\textcolor{white}{5}}}child{node{\textcolor{white}{6}}}}}
child{node{\textcolor{white}{7}}child{node{\textcolor{white}{8}}}child{node{\textcolor{white}{9}}}child{node{\textcolor{white}{11}}}}
child{node{\textcolor{white}{\textcolor{white}{12}}}child{node{\textcolor{white}{10}}child{node{\textcolor{white}{13}}}child{node{\textcolor{white}{14}}}}};
    \end{tikzpicture}
    }
 \end{frame}

 
 
 
 
 
  \begin{frame}
   \frametitle{Parcours en profondeur d'un arbre}
   
    \hspace{2cm}\scalebox{0.5}{
   \begin{tikzpicture}[every node/.style={circle,draw},
level 1/.style={sibling distance=5cm,level distance=4cm},
level 2/.style={sibling distance=2cm,level distance=4cm},
level 3/.style={sibling distance=2cm,level distance=4cm}]
  \node[fill,color=gray!25]{\textcolor{white}{1}}
child{node{\textcolor{white}{2}}child{node{\textcolor{white}{3 }}}child{node{\textcolor{white}{4}}child{node{\textcolor{white}{5}}}child{node{\textcolor{white}{6}}}}}
child{node{\textcolor{white}{7}}child{node{\textcolor{white}{8}}}child{node{\textcolor{white}{9}}}child{node{\textcolor{white}{11}}}}
child{node{\textcolor{white}{\textcolor{white}{12}}}child{node{\textcolor{white}{10}}child{node{\textcolor{white}{13}}}child{node{\textcolor{white}{14}}}}};
    \end{tikzpicture}
    }
 \end{frame}

  
  \begin{frame}
   \frametitle{Parcours en profondeur d'un arbre}
    
   
    \hspace{2cm}\scalebox{0.5}{
   \begin{tikzpicture}[every node/.style={circle,draw},
level 1/.style={sibling distance=5cm,level distance=4cm},
level 2/.style={sibling distance=2cm,level distance=4cm},
level 3/.style={sibling distance=2cm,level distance=4cm}]
  \node[fill,color=gray!25]{\textcolor{white}{1}}
child{node[fill,color=gray!25]{\textcolor{white}{2}}child{node{\textcolor{white}{3 }}}child{node{\textcolor{white}{4}}child{node{\textcolor{white}{5}}}child{node{\textcolor{white}{6}}}}}
child{node{\textcolor{white}{7}}child{node{\textcolor{white}{8}}}child{node{\textcolor{white}{9}}}child{node{\textcolor{white}{11}}}}
child{node{\textcolor{white}{\textcolor{white}{12}}}child{node{\textcolor{white}{10}}child{node{\textcolor{white}{13}}}child{node{\textcolor{white}{14}}}}};
    \end{tikzpicture}
    }
 \end{frame}

 
 
 
  
   \begin{frame}
   \frametitle{Parcours en profondeur d'un arbre}
    
   
    \hspace{2cm}\scalebox{0.5}{
   \begin{tikzpicture}[every node/.style={circle,draw},
level 1/.style={sibling distance=5cm,level distance=4cm},
level 2/.style={sibling distance=2cm,level distance=4cm},
level 3/.style={sibling distance=2cm,level distance=4cm}]
  \node[fill,color=gray!25]{\textcolor{white}{1}}
child{node[fill,color=gray!25]{\textcolor{white}{2}}child{node[fill,color=gray!25]{\textcolor{white}{3 }}}child{node{\textcolor{white}{4}}child{node{\textcolor{white}{5}}}child{node{\textcolor{white}{6}}}}}
child{node{\textcolor{white}{7}}child{node{\textcolor{white}{8}}}child{node{\textcolor{white}{9}}}child{node{\textcolor{white}{11}}}}
child{node{\textcolor{white}{\textcolor{white}{12}}}child{node{\textcolor{white}{10}}child{node{\textcolor{white}{13}}}child{node{\textcolor{white}{14}}}}};
    \end{tikzpicture}
    }
 \end{frame}

  \begin{frame}
   \frametitle{Parcours en profondeur d'un arbre}
    
   
    \hspace{2cm}\scalebox{0.5}{
   \begin{tikzpicture}[every node/.style={circle,draw},
level 1/.style={sibling distance=5cm,level distance=4cm},
level 2/.style={sibling distance=2cm,level distance=4cm},
level 3/.style={sibling distance=2cm,level distance=4cm}]
  \node[fill,color=gray!25]{\textcolor{white}{1}}
child{node[fill,color=gray!25]{\textcolor{white}{2}}child{node[fill,color=black]{\textcolor{white}{3 }}}child{node{\textcolor{white}{4}}child{node{\textcolor{white}{5}}}child{node{\textcolor{white}{6}}}}}
child{node{\textcolor{white}{7}}child{node{\textcolor{white}{8}}}child{node{\textcolor{white}{9}}}child{node{\textcolor{white}{11}}}}
child{node{\textcolor{white}{\textcolor{white}{12}}}child{node{\textcolor{white}{10}}child{node{\textcolor{white}{13}}}child{node{\textcolor{white}{14}}}}};
    \end{tikzpicture}
    }
 \end{frame}

 
   \begin{frame}
   \frametitle{Parcours en profondeur d'un arbre}
    
   
    \hspace{2cm}\scalebox{0.5}{
   \begin{tikzpicture}[every node/.style={circle,draw},
level 1/.style={sibling distance=5cm,level distance=4cm},
level 2/.style={sibling distance=2cm,level distance=4cm},
level 3/.style={sibling distance=2cm,level distance=4cm}]
  \node[fill,color=gray!25]{\textcolor{white}{1}}
child{node[fill,color=gray!25]{\textcolor{white}{2}}child{node[fill,color=black]{\textcolor{white}{3 }}}child{node[fill,color=gray!25]{\textcolor{white}{4}}child{node{\textcolor{white}{5}}}child{node{\textcolor{white}{6}}}}}
child{node{\textcolor{white}{7}}child{node{\textcolor{white}{8}}}child{node{\textcolor{white}{9}}}child{node{\textcolor{white}{11}}}}
child{node{\textcolor{white}{\textcolor{white}{12}}}child{node{\textcolor{white}{10}}child{node{\textcolor{white}{13}}}child{node{\textcolor{white}{14}}}}};
    \end{tikzpicture}
    }
 \end{frame}
  
  
  
  \begin{frame}
   \frametitle{Parcours en profondeur d'un arbre}
    \hspace{2cm}\scalebox{0.5}{
   \begin{tikzpicture}[every node/.style={circle,draw},
level 1/.style={sibling distance=5cm,level distance=4cm},
level 2/.style={sibling distance=2cm,level distance=4cm},
level 3/.style={sibling distance=2cm,level distance=4cm}]
  \node[fill,color=gray!25]{\textcolor{white}{1}}
child{node[fill,color=gray!25]{\textcolor{white}{2}}child{node[fill,color=black]{\textcolor{white}{3 }}}child{node[fill,color=gray!25]{\textcolor{white}{4}}child{node[fill,color=gray!25]{\textcolor{white}{5}}}child{node{\textcolor{white}{6}}}}}
child{node{\textcolor{white}{7}}child{node{\textcolor{white}{8}}}child{node{\textcolor{white}{9}}}child{node{\textcolor{white}{11}}}}
child{node{\textcolor{white}{\textcolor{white}{12}}}child{node{\textcolor{white}{10}}child{node{\textcolor{white}{13}}}child{node{\textcolor{white}{14}}}}};
    \end{tikzpicture}
    }
 \end{frame}
 
 
 \begin{frame}
   \frametitle{Parcours en profondeur d'un arbre}
    \hspace{2cm}\scalebox{0.5}{
   \begin{tikzpicture}[every node/.style={circle,draw},
level 1/.style={sibling distance=5cm,level distance=4cm},
level 2/.style={sibling distance=2cm,level distance=4cm},
level 3/.style={sibling distance=2cm,level distance=4cm}]
  \node[fill,color=gray!25]{\textcolor{white}{1}}
child{node[fill,color=gray!25]{\textcolor{white}{2}}child{node[fill,color=black]{\textcolor{white}{3 }}}child{node[fill,color=gray!25]{\textcolor{white}{4}}child{node[fill,color=black]{\textcolor{white}{5}}}child{node{\textcolor{white}{6}}}}}
child{node{\textcolor{white}{7}}child{node{\textcolor{white}{8}}}child{node{\textcolor{white}{9}}}child{node{\textcolor{white}{11}}}}
child{node{\textcolor{white}{\textcolor{white}{12}}}child{node{\textcolor{white}{10}}child{node{\textcolor{white}{13}}}child{node{\textcolor{white}{14}}}}};
    \end{tikzpicture}
    }
 \end{frame}
 
 
 \begin{frame}
   \frametitle{Parcours en profondeur d'un arbre}
    \hspace{2cm}\scalebox{0.5}{
   \begin{tikzpicture}[every node/.style={circle,draw},
level 1/.style={sibling distance=5cm,level distance=4cm},
level 2/.style={sibling distance=2cm,level distance=4cm},
level 3/.style={sibling distance=2cm,level distance=4cm}]
  \node[fill,color=gray!25]{\textcolor{white}{1}}
child{node[fill,color=gray!25]{\textcolor{white}{2}}child{node[fill,color=black]{\textcolor{white}{3 }}}child{node[fill,color=gray!25]{\textcolor{white}{4}}child{node[fill,color=black]{\textcolor{white}{5}}}child{node[fill,color=gray!25]{\textcolor{white}{6}}}}}
child{node{\textcolor{white}{7}}child{node{\textcolor{white}{8}}}child{node{\textcolor{white}{9}}}child{node{\textcolor{white}{11}}}}
child{node{\textcolor{white}{\textcolor{white}{12}}}child{node{\textcolor{white}{10}}child{node{\textcolor{white}{13}}}child{node{\textcolor{white}{14}}}}};
    \end{tikzpicture}
    }
 \end{frame}
 
 
 
 
 \begin{frame}
   \frametitle{Parcours en profondeur d'un arbre}
    \hspace{2cm}\scalebox{0.5}{
   \begin{tikzpicture}[every node/.style={circle,draw},
level 1/.style={sibling distance=5cm,level distance=4cm},
level 2/.style={sibling distance=2cm,level distance=4cm},
level 3/.style={sibling distance=2cm,level distance=4cm}]
  \node[fill,color=gray!25]{\textcolor{white}{1}}
child{node[fill,color=gray!25]{\textcolor{white}{2}}child{node[fill,color=black]{\textcolor{white}{3 }}}child{node[fill,color=gray!25]{\textcolor{white}{4}}child{node[fill,color=black]{\textcolor{white}{5}}}child{node[fill,color=black]{\textcolor{white}{6}}}}}
child{node{\textcolor{white}{7}}child{node{\textcolor{white}{8}}}child{node{\textcolor{white}{9}}}child{node{\textcolor{white}{11}}}}
child{node{\textcolor{white}{\textcolor{white}{12}}}child{node{\textcolor{white}{10}}child{node{\textcolor{white}{13}}}child{node{\textcolor{white}{14}}}}};
    \end{tikzpicture}
    }
 \end{frame}
 
  
  
  
  \begin{frame}
   \frametitle{Parcours en profondeur d'un arbre}
    \hspace{2cm}\scalebox{0.5}{
   \begin{tikzpicture}[every node/.style={circle,draw},
level 1/.style={sibling distance=5cm,level distance=4cm},
level 2/.style={sibling distance=2cm,level distance=4cm},
level 3/.style={sibling distance=2cm,level distance=4cm}]
  \node[fill,color=gray!25]{\textcolor{white}{1}}
child{node[fill,color=gray!25]{\textcolor{white}{2}}child{node[fill,color=black]{\textcolor{white}{3 }}}child{node[fill,color=black]{\textcolor{white}{4}}child{node[fill,color=black]{\textcolor{white}{5}}}child{node[fill,color=black]{\textcolor{white}{6}}}}}
child{node{\textcolor{white}{7}}child{node{\textcolor{white}{8}}}child{node{\textcolor{white}{9}}}child{node{\textcolor{white}{11}}}}
child{node{\textcolor{white}{\textcolor{white}{12}}}child{node{\textcolor{white}{10}}child{node{\textcolor{white}{13}}}child{node{\textcolor{white}{14}}}}};
    \end{tikzpicture}
    }
 \end{frame}
  
  
  \begin{frame}
   \frametitle{Parcours en profondeur d'un arbre}
    \hspace{2cm}\scalebox{0.5}{
   \begin{tikzpicture}[every node/.style={circle,draw},
level 1/.style={sibling distance=5cm,level distance=4cm},
level 2/.style={sibling distance=2cm,level distance=4cm},
level 3/.style={sibling distance=2cm,level distance=4cm}]
  \node[fill,color=gray!25]{\textcolor{white}{1}}
child{node[fill,color=black]{\textcolor{white}{2}}child{node[fill,color=black]{\textcolor{white}{3 }}}child{node[fill,color=black]{\textcolor{white}{4}}child{node[fill,color=black]{\textcolor{white}{5}}}child{node[fill,color=black]{\textcolor{white}{6}}}}}
child{node{\textcolor{white}{7}}child{node{\textcolor{white}{8}}}child{node{\textcolor{white}{9}}}child{node{\textcolor{white}{11}}}}
child{node{\textcolor{white}{\textcolor{white}{12}}}child{node{\textcolor{white}{10}}child{node{\textcolor{white}{13}}}child{node{\textcolor{white}{14}}}}};
    \end{tikzpicture}
    }
 \end{frame}
  
  
  \begin{frame}
   \frametitle{Parcours en profondeur d'un arbre}
    \hspace{2cm}\scalebox{0.5}{
   \begin{tikzpicture}[every node/.style={circle,draw},
level 1/.style={sibling distance=5cm,level distance=4cm},
level 2/.style={sibling distance=2cm,level distance=4cm},
level 3/.style={sibling distance=2cm,level distance=4cm}]
  \node[fill,color=gray!25]{\textcolor{white}{1}}
child{node[fill,color=black]{\textcolor{white}{2}}child{node[fill,color=black]{\textcolor{white}{3 }}}child{node[fill,color=black]{\textcolor{white}{4}}child{node[fill,color=black]{\textcolor{white}{5}}}child{node[fill,color=black]{\textcolor{white}{6}}}}}
child{node[fill,color=gray!25]{\textcolor{white}{7}}child{node{\textcolor{white}{8}}}child{node{\textcolor{white}{9}}}child{node{\textcolor{white}{11}}}}
child{node{\textcolor{white}{\textcolor{white}{12}}}child{node{\textcolor{white}{10}}child{node{\textcolor{white}{13}}}child{node{\textcolor{white}{14}}}}};
    \end{tikzpicture}
    }
 \end{frame}
 
 
 
  \begin{frame}
   \frametitle{Parcours en profondeur d'un arbre}
    \hspace{2cm}\scalebox{0.5}{
   \begin{tikzpicture}[every node/.style={circle,draw},
level 1/.style={sibling distance=5cm,level distance=4cm},
level 2/.style={sibling distance=2cm,level distance=4cm},
level 3/.style={sibling distance=2cm,level distance=4cm}]
  \node[fill,color=gray!25]{\textcolor{white}{1}}
child{node[fill,color=black]{\textcolor{white}{2}}child{node[fill,color=black]{\textcolor{white}{3 }}}child{node[fill,color=black]{\textcolor{white}{4}}child{node[fill,color=black]{\textcolor{white}{5}}}child{node[fill,color=black]{\textcolor{white}{6}}}}}
child{node[fill,color=gray!25]{\textcolor{white}{7}}child{node[fill,color=gray!25]{\textcolor{white}{8}}}child{node{\textcolor{white}{9}}}child{node{\textcolor{white}{11}}}}
child{node{\textcolor{white}{\textcolor{white}{12}}}child{node{\textcolor{white}{10}}child{node{\textcolor{white}{13}}}child{node{\textcolor{white}{14}}}}};
    \end{tikzpicture}
    }
 \end{frame}
 
 
 
 
  \begin{frame}
   \frametitle{Parcours en profondeur d'un arbre}
    \hspace{2cm}\scalebox{0.5}{
   \begin{tikzpicture}[every node/.style={circle,draw},
level 1/.style={sibling distance=5cm,level distance=4cm},
level 2/.style={sibling distance=2cm,level distance=4cm},
level 3/.style={sibling distance=2cm,level distance=4cm}]
  \node[fill,color=gray!25]{\textcolor{white}{1}}
child{node[fill,color=black]{\textcolor{white}{2}}child{node[fill,color=black]{\textcolor{white}{3 }}}child{node[fill,color=black]{\textcolor{white}{4}}child{node[fill,color=black]{\textcolor{white}{5}}}child{node[fill,color=black]{\textcolor{white}{6}}}}}
child{node[fill,color=gray!25]{\textcolor{white}{7}}child{node[fill,color=black]{\textcolor{white}{8}}}child{node{\textcolor{white}{9}}}child{node{\textcolor{white}{11}}}}
child{node{\textcolor{white}{\textcolor{white}{12}}}child{node{\textcolor{white}{10}}child{node{\textcolor{white}{13}}}child{node{\textcolor{white}{14}}}}};
    \end{tikzpicture}
    }
 \end{frame}
 
 
 
  \begin{frame}
   \frametitle{Parcours en profondeur d'un arbre}
    \hspace{2cm}\scalebox{0.5}{
   \begin{tikzpicture}[every node/.style={circle,draw},
level 1/.style={sibling distance=5cm,level distance=4cm},
level 2/.style={sibling distance=2cm,level distance=4cm},
level 3/.style={sibling distance=2cm,level distance=4cm}]
  \node[fill,color=gray!25]{\textcolor{white}{1}}
child{node[fill,color=black]{\textcolor{white}{2}}child{node[fill,color=black]{\textcolor{white}{3 }}}child{node[fill,color=black]{\textcolor{white}{4}}child{node[fill,color=black]{\textcolor{white}{5}}}child{node[fill,color=black]{\textcolor{white}{6}}}}}
child{node[fill,color=gray!25]{\textcolor{white}{7}}child{node[fill,color=black]{\textcolor{white}{8}}}child{node[fill,color=gray!25]{\textcolor{white}{9}}}child{node{\textcolor{white}{11}}}}
child{node{\textcolor{white}{\textcolor{white}{12}}}child{node{\textcolor{white}{10}}child{node{\textcolor{white}{13}}}child{node{\textcolor{white}{14}}}}};
    \end{tikzpicture}
    }
 \end{frame}
 
 
 
  \begin{frame}
   \frametitle{Parcours en profondeur d'un arbre}
    \hspace{2cm}\scalebox{0.5}{
   \begin{tikzpicture}[every node/.style={circle,draw},
level 1/.style={sibling distance=5cm,level distance=4cm},
level 2/.style={sibling distance=2cm,level distance=4cm},
level 3/.style={sibling distance=2cm,level distance=4cm}]
  \node[fill,color=gray!25]{\textcolor{white}{1}}
child{node[fill,color=black]{\textcolor{white}{2}}child{node[fill,color=black]{\textcolor{white}{3 }}}child{node[fill,color=black]{\textcolor{white}{4}}child{node[fill,color=black]{\textcolor{white}{5}}}child{node[fill,color=black]{\textcolor{white}{6}}}}}
child{node[fill,color=gray!25]{\textcolor{white}{7}}child{node[fill,color=black]{\textcolor{white}{8}}}child{node[fill,color=black]{\textcolor{white}{9}}}child{node{\textcolor{white}{11}}}}
child{node{\textcolor{white}{\textcolor{white}{12}}}child{node{\textcolor{white}{10}}child{node{\textcolor{white}{13}}}child{node{\textcolor{white}{14}}}}};
    \end{tikzpicture}
    }
 \end{frame}
  
   
 
  
  \begin{frame}
   \frametitle{Parcours en profondeur d'un arbre}
    \hspace{2cm}\scalebox{0.5}{
   \begin{tikzpicture}[every node/.style={circle,draw},
level 1/.style={sibling distance=5cm,level distance=4cm},
level 2/.style={sibling distance=2cm,level distance=4cm},
level 3/.style={sibling distance=2cm,level distance=4cm}]
  \node[fill,color=gray!25]{\textcolor{white}{1}}
child{node[fill,color=black]{\textcolor{white}{2}}child{node[fill,color=black]{\textcolor{white}{3 }}}child{node[fill,color=black]{\textcolor{white}{4}}child{node[fill,color=black]{\textcolor{white}{5}}}child{node[fill,color=black]{\textcolor{white}{6}}}}}
child{node[fill,color=gray!25]{\textcolor{white}{7}}child{node[fill,color=black]{\textcolor{white}{8}}}child{node[fill,color=black]{\textcolor{white}{9}}}child{node[fill,color=gray!25]{\textcolor{white}{10}}}}
child{node{\textcolor{white}{\textcolor{white}{12}}}child{node{\textcolor{white}{10}}child{node{\textcolor{white}{13}}}child{node{\textcolor{white}{14}}}}};
    \end{tikzpicture}
    }
 \end{frame}
  
  
  \begin{frame}
   \frametitle{Parcours en profondeur d'un arbre}
    \hspace{2cm}\scalebox{0.5}{
   \begin{tikzpicture}[every node/.style={circle,draw},
level 1/.style={sibling distance=5cm,level distance=4cm},
level 2/.style={sibling distance=2cm,level distance=4cm},
level 3/.style={sibling distance=2cm,level distance=4cm}]
  \node[fill,color=gray!25]{\textcolor{white}{1}}
child{node[fill,color=black]{\textcolor{white}{2}}child{node[fill,color=black]{\textcolor{white}{3 }}}child{node[fill,color=black]{\textcolor{white}{4}}child{node[fill,color=black]{\textcolor{white}{5}}}child{node[fill,color=black]{\textcolor{white}{6}}}}}
child{node[fill,color=gray!25]{\textcolor{white}{7}}child{node[fill,color=black]{\textcolor{white}{8}}}child{node[fill,color=black]{\textcolor{white}{9}}}child{node[fill,color=black]{\textcolor{white}{10}}}}
child{node{\textcolor{white}{\textcolor{white}{12}}}child{node{\textcolor{white}{10}}child{node{\textcolor{white}{13}}}child{node{\textcolor{white}{14}}}}};
    \end{tikzpicture}
    }
 \end{frame}  
 
 
  
 
 
 
 
  \begin{frame}
   \frametitle{Parcours en profondeur d'un arbre}
    \hspace{2cm}\scalebox{0.5}{
   \begin{tikzpicture}[every node/.style={circle,draw},
level 1/.style={sibling distance=5cm,level distance=4cm},
level 2/.style={sibling distance=2cm,level distance=4cm},
level 3/.style={sibling distance=2cm,level distance=4cm}]
  \node[fill,color=gray!25]{\textcolor{white}{1}}
child{node[fill,color=black]{\textcolor{white}{2}}child{node[fill,color=black]{\textcolor{white}{3 }}}child{node[fill,color=black]{\textcolor{white}{4}}child{node[fill,color=black]{\textcolor{white}{5}}}child{node[fill,color=black]{\textcolor{white}{6}}}}}
child{node[fill,color=black]{\textcolor{white}{7}}child{node[fill,color=black]{\textcolor{white}{8}}}child{node[fill,color=black]{\textcolor{white}{9}}}child{node[fill,color=black]{\textcolor{white}{10}}}}
child{node[fill,color=gray!25]{\textcolor{white}{\textcolor{white}{11}}}child{node{\textcolor{white}{12}}child{node{\textcolor{white}{13}}}child{node{\textcolor{white}{14}}}}};
    \end{tikzpicture}
    }
 \end{frame}  
    
    
    
    \begin{frame}
   \frametitle{Parcours en profondeur d'un arbre}
    \hspace{2cm}\scalebox{0.5}{
   \begin{tikzpicture}[every node/.style={circle,draw},
level 1/.style={sibling distance=5cm,level distance=4cm},
level 2/.style={sibling distance=2cm,level distance=4cm},
level 3/.style={sibling distance=2cm,level distance=4cm}]
  \node[fill,color=gray!25]{\textcolor{white}{1}}
child{node[fill,color=black]{\textcolor{white}{2}}child{node[fill,color=black]{\textcolor{white}{3 }}}child{node[fill,color=black]{\textcolor{white}{4}}child{node[fill,color=black]{\textcolor{white}{5}}}child{node[fill,color=black]{\textcolor{white}{6}}}}}
child{node[fill,color=black]{\textcolor{white}{7}}child{node[fill,color=black]{\textcolor{white}{8}}}child{node[fill,color=black]{\textcolor{white}{9}}}child{node[fill,color=black]{\textcolor{white}{10}}}}
child{node[fill,color=gray!25]{\textcolor{white}{\textcolor{white}{11}}}child{node[fill,color=gray!25]{\textcolor{white}{12}}child{node{\textcolor{white}{13}}}child{node{\textcolor{white}{14}}}}};
    \end{tikzpicture}
    }
 \end{frame}  
 
 
 
 
 
 
    \begin{frame}
   \frametitle{Parcours en profondeur d'un arbre}
    \hspace{2cm}\scalebox{0.5}{
   \begin{tikzpicture}[every node/.style={circle,draw},
level 1/.style={sibling distance=5cm,level distance=4cm},
level 2/.style={sibling distance=2cm,level distance=4cm},
level 3/.style={sibling distance=2cm,level distance=4cm}]
  \node[fill,color=gray!25]{\textcolor{white}{1}}
child{node[fill,color=black]{\textcolor{white}{2}}child{node[fill,color=black]{\textcolor{white}{3 }}}child{node[fill,color=black]{\textcolor{white}{4}}child{node[fill,color=black]{\textcolor{white}{5}}}child{node[fill,color=black]{\textcolor{white}{6}}}}}
child{node[fill,color=black]{\textcolor{white}{7}}child{node[fill,color=black]{\textcolor{white}{8}}}child{node[fill,color=black]{\textcolor{white}{9}}}child{node[fill,color=black]{\textcolor{white}{10}}}}
child{node[fill,color=gray!25]{\textcolor{white}{\textcolor{white}{11}}}child{node[fill,color=gray!25]{\textcolor{white}{12}}child{node[fill,color=gray!25]{\textcolor{white}{13}}}child{node{\textcolor{white}{14}}}}};
    \end{tikzpicture}
    }
 \end{frame}  
 
 
 
 
    \begin{frame}
   \frametitle{Parcours en profondeur d'un arbre}
    \hspace{2cm}\scalebox{0.5}{
   \begin{tikzpicture}[every node/.style={circle,draw},
level 1/.style={sibling distance=5cm,level distance=4cm},
level 2/.style={sibling distance=2cm,level distance=4cm},
level 3/.style={sibling distance=2cm,level distance=4cm}]
  \node[fill,color=gray!25]{\textcolor{white}{1}}
child{node[fill,color=black]{\textcolor{white}{2}}child{node[fill,color=black]{\textcolor{white}{3 }}}child{node[fill,color=black]{\textcolor{white}{4}}child{node[fill,color=black]{\textcolor{white}{5}}}child{node[fill,color=black]{\textcolor{white}{6}}}}}
child{node[fill,color=black]{\textcolor{white}{7}}child{node[fill,color=black]{\textcolor{white}{8}}}child{node[fill,color=black]{\textcolor{white}{9}}}child{node[fill,color=black]{\textcolor{white}{10}}}}
child{node[fill,color=gray!25]{\textcolor{white}{\textcolor{white}{11}}}child{node[fill,color=gray!25]{\textcolor{white}{12}}child{node[fill,color=black]{\textcolor{white}{13}}}child{node{\textcolor{white}{14}}}}};
    \end{tikzpicture}
    }
 \end{frame}  
    
    
    \begin{frame}
   \frametitle{Parcours en profondeur d'un arbre}
    \hspace{2cm}\scalebox{0.5}{
   \begin{tikzpicture}[every node/.style={circle,draw},
level 1/.style={sibling distance=5cm,level distance=4cm},
level 2/.style={sibling distance=2cm,level distance=4cm},
level 3/.style={sibling distance=2cm,level distance=4cm}]
  \node[fill,color=gray!25]{\textcolor{white}{1}}
child{node[fill,color=black]{\textcolor{white}{2}}child{node[fill,color=black]{\textcolor{white}{3 }}}child{node[fill,color=black]{\textcolor{white}{4}}child{node[fill,color=black]{\textcolor{white}{5}}}child{node[fill,color=black]{\textcolor{white}{6}}}}}
child{node[fill,color=black]{\textcolor{white}{7}}child{node[fill,color=black]{\textcolor{white}{8}}}child{node[fill,color=black]{\textcolor{white}{9}}}child{node[fill,color=black]{\textcolor{white}{10}}}}
child{node[fill,color=gray!25]{\textcolor{white}{\textcolor{white}{11}}}child{node[fill,color=gray!25]{\textcolor{white}{12}}child{node[fill,color=black]{\textcolor{white}{13}}}child{node[fill,color=gray!25]{\textcolor{white}{14}}}}};
    \end{tikzpicture}
    }
 \end{frame}  
 
 
 
    \begin{frame}
   \frametitle{Parcours en profondeur d'un arbre}
    \hspace{2cm}\scalebox{0.5}{
   \begin{tikzpicture}[every node/.style={circle,draw},
level 1/.style={sibling distance=5cm,level distance=4cm},
level 2/.style={sibling distance=2cm,level distance=4cm},
level 3/.style={sibling distance=2cm,level distance=4cm}]
  \node[fill,color=gray!25]{\textcolor{white}{1}}
child{node[fill,color=black]{\textcolor{white}{2}}child{node[fill,color=black]{\textcolor{white}{3 }}}child{node[fill,color=black]{\textcolor{white}{4}}child{node[fill,color=black]{\textcolor{white}{5}}}child{node[fill,color=black]{\textcolor{white}{6}}}}}
child{node[fill,color=black]{\textcolor{white}{7}}child{node[fill,color=black]{\textcolor{white}{8}}}child{node[fill,color=black]{\textcolor{white}{9}}}child{node[fill,color=black]{\textcolor{white}{10}}}}
child{node[fill,color=gray!25]{\textcolor{white}{\textcolor{white}{11}}}child{node[fill,color=gray!25]{\textcolor{white}{12}}child{node[fill,color=black]{\textcolor{white}{13}}}child{node[fill,color=black]{\textcolor{white}{14}}}}};
    \end{tikzpicture}
    }
 \end{frame}  
 
 
    \begin{frame}
   \frametitle{Parcours en profondeur d'un arbre}
    \hspace{2cm}\scalebox{0.5}{
   \begin{tikzpicture}[every node/.style={circle,draw},
level 1/.style={sibling distance=5cm,level distance=4cm},
level 2/.style={sibling distance=2cm,level distance=4cm},
level 3/.style={sibling distance=2cm,level distance=4cm}]
  \node[fill,color=gray!25]{\textcolor{white}{1}}
child{node[fill,color=black]{\textcolor{white}{2}}child{node[fill,color=black]{\textcolor{white}{3 }}}child{node[fill,color=black]{\textcolor{white}{4}}child{node[fill,color=black]{\textcolor{white}{5}}}child{node[fill,color=black]{\textcolor{white}{6}}}}}
child{node[fill,color=black]{\textcolor{white}{7}}child{node[fill,color=black]{\textcolor{white}{8}}}child{node[fill,color=black]{\textcolor{white}{9}}}child{node[fill,color=black]{\textcolor{white}{10}}}}
child{node[fill,color=gray!25]{\textcolor{white}{\textcolor{white}{11}}}child{node[fill,color=black]{\textcolor{white}{12}}child{node[fill,color=black]{\textcolor{white}{13}}}child{node[fill,color=black]{\textcolor{white}{14}}}}};
    \end{tikzpicture}
    }
 \end{frame}  
 
 
 
    \begin{frame}
   \frametitle{Parcours en profondeur d'un arbre}
    \hspace{2cm}\scalebox{0.5}{
   \begin{tikzpicture}[every node/.style={circle,draw},
level 1/.style={sibling distance=5cm,level distance=4cm},
level 2/.style={sibling distance=2cm,level distance=4cm},
level 3/.style={sibling distance=2cm,level distance=4cm}]
  \node[fill,color=gray!25]{\textcolor{white}{1}}
child{node[fill,color=black]{\textcolor{white}{2}}child{node[fill,color=black]{\textcolor{white}{3 }}}child{node[fill,color=black]{\textcolor{white}{4}}child{node[fill,color=black]{\textcolor{white}{5}}}child{node[fill,color=black]{\textcolor{white}{6}}}}}
child{node[fill,color=black]{\textcolor{white}{7}}child{node[fill,color=black]{\textcolor{white}{8}}}child{node[fill,color=black]{\textcolor{white}{9}}}child{node[fill,color=black]{\textcolor{white}{10}}}}
child{node[fill,color=black]{\textcolor{white}{\textcolor{white}{11}}}child{node[fill,color=black]{\textcolor{white}{12}}child{node[fill,color=black]{\textcolor{white}{13}}}child{node[fill,color=black]{\textcolor{white}{14}}}}};
    \end{tikzpicture}
    }
 \end{frame}  
 
 
 
    \begin{frame}
   \frametitle{Parcours en profondeur d'un arbre}
    \hspace{2cm}\scalebox{0.5}{
   \begin{tikzpicture}[every node/.style={circle,draw},
level 1/.style={sibling distance=5cm,level distance=4cm},
level 2/.style={sibling distance=2cm,level distance=4cm},
level 3/.style={sibling distance=2cm,level distance=4cm}]
  \node[fill,color=black]{\textcolor{white}{1}}
child{node[fill,color=black]{\textcolor{white}{2}}child{node[fill,color=black]{\textcolor{white}{3 }}}child{node[fill,color=black]{\textcolor{white}{4}}child{node[fill,color=black]{\textcolor{white}{5}}}child{node[fill,color=black]{\textcolor{white}{6}}}}}
child{node[fill,color=black]{\textcolor{white}{7}}child{node[fill,color=black]{\textcolor{white}{8}}}child{node[fill,color=black]{\textcolor{white}{9}}}child{node[fill,color=black]{\textcolor{white}{10}}}}
child{node[fill,color=black]{\textcolor{white}{\textcolor{white}{11}}}child{node[fill,color=black]{\textcolor{white}{12}}child{node[fill,color=black]{\textcolor{white}{13}}}child{node[fill,color=black]{\textcolor{white}{14}}}}};
    \end{tikzpicture}
    }
    \href{run:arbre/arbredfs.py}{\beamerbutton{arbre DFS en python}}
 \end{frame}  
 
 
 
 
 
 
    \begin{frame}
     \frametitle{DFS (depth first search) : programmation python}
     
     \textbf{Exercice à rendre 3.}
     
     Avec la représentation d'un graphe par un dictionnaire comme précédemment, programmer en langage python le DFS avec les variables suivantes :
   \begin{itemize}
    \item<1-> Un dictionnaire P. En fin de parcours, pour tout sommet s du graphe P[s] sera le père de s, c'est à dire le sommet à partir duquel le sommet s a été découvert lors du parcours.
    \item<2-> Un dictionnaire couleur. Pour tout sommet s, couleur[s] vaut blanc si le sommet s n'est pas encore découvert, gris s'il est déjà découvert mais non encore fermé (c'est à dire si l'algorithme n' a pas encore découvert tous ses voisins), noir lorsque ce sommet est fermé.
    \item<3-> Une liste Q utilisée comme pile (lifo) : on empile un sommet lorsqu'il est découvert, on le dépile lorsqu'il est terminé (traitement prioritaire des sommets découverts au plus tard).
   \end{itemize}
    \end{frame}

   
         
         
         \begin{frame}
 \frametitle{Exemple d'exécution}
        
   
   
   Déroulement attendu du  programme, avec l'appel   dfs(G,'g'),  sur le graphe ci-dessous :
   
  

\begin{minipage}{5cm}
 \begin{codepython}
G=dict()

G['a']=['b','c']

G['b']=['a','d','e']

G['c']=['a','d']

G['d']=['b','c','e']

G['e']=['b','d','f','g']

G['f']=['e','g']

G['g']=['e','f','h']

G['h']=['g']
\end{codepython} 
\end{minipage}
\begin{minipage}{5cm}
\begin{tikzpicture}
\path
(0,1) node[draw](a){$a$}
(1,2) node[draw](b){$b$}
(1,0) node[draw ](c){$c$}
(2,1) node[draw](d){$d$}
(3,2) node[draw](e){$e$}
(5,2) node[draw](f){$f$}
(4,1) node[draw](g){$g$}
(3,0) node[draw](h){$h$};
\draw  (a)--(b); \draw  (a)--(c); 
\draw  (b)--(d); \draw  (b)--(e); 
\draw  (d)--(c); \draw  (d)--(e); 
\draw  (e)--(f); \draw  (f)--(g); 
\draw  (g)--(h); \draw  (e)--(g); 
\end{tikzpicture}
\end{minipage}
         \end{frame}
         
         \begin{frame}
     \frametitle{Déroulement}
     \begin{tikzpicture}
\path
(0,1) node[draw](a){$a$}
(1,2) node[draw](b){$b$}
(1,0) node[draw ](c){$c$}
(2,1) node[draw](d){$d$}
(3,2) node[draw](e){$e$}
(5,2) node[draw](f){$f$}
(4,1) node[draw,fill,gray!20](g){\color{white}{$g$}}
(3,0) node[draw](h){$h$};
\draw  (a)--(b); \draw  (a)--(c); 
\draw  (b)--(d); \draw  (b)--(e); 
\draw  (d)--(c); \draw  (d)--(e); 
\draw  (e)--(f); \draw  (f)--(g); 
\draw  (g)--(h); \draw (g)--(e); 
\end{tikzpicture}

P=\{ g: None\}

Q=[g]

Découverts (gris ou noirs)=[g]

Fermés (noirs) =[]
         \end{frame}
         
          \begin{frame}
     \frametitle{Déroulement}
     \begin{tikzpicture}[>=triangle 45]
\path
(0,1) node[draw](a){$a$}
(1,2) node[draw](b){$b$}
(1,0) node[draw ](c){$c$}
(2,1) node[draw](d){$d$}
(3,2) node[draw,fill,gray!20](e){\color{white}{$e$}}
(5,2) node[draw](f){$f$}
(4,1) node[draw,fill,gray!20](g){\color{white}{$g$}}
(3,0) node[draw](h){$h$};
\draw  (a)--(b); \draw  (a)--(c); 
\draw  (b)--(d); \draw  (b)--(e); 
\draw  (d)--(c); \draw  (d)--(e); 
\draw  (e)--(f); \draw  (f)--(g); 
\draw  (g)--(h); \draw[<-]  (e)--(g); 
\end{tikzpicture}
u=g, R=[e,f,h],v=e,

P=\{ g: None, e : g\}

Q=[g,e]

Découverts=[g,e]

Fermés=[]

         \end{frame}
         
          \begin{frame}
     \frametitle{Déroulement}
     \begin{tikzpicture}[>=triangle 45]
\path
(0,1) node[draw](a){$a$}
(1,2) node[draw,fill,gray!20](b){\color{white}{$b$}}
(1,0) node[draw ](c){$c$}
(2,1) node[draw](d){$d$}
(3,2) node[draw,fill,gray!20](e){\color{white}{$e$}}
(5,2) node[draw](f){$f$}
(4,1) node[draw,fill,gray!20](g){\color{white}{$g$}}
(3,0) node[draw](h){$h$};
\draw  (a)--(b); \draw  (a)--(c); 
\draw  (b)--(d); \draw[<-]  (b)--(e); 
\draw  (d)--(c); \draw  (d)--(e); 
\draw  (e)--(f); \draw  (f)--(g); 
\draw  (g)--(h); \draw[<-]  (e)--(g); 
\end{tikzpicture}
u=e, R=[b,d,f],v=b,

P=\{ g: None, e : g,b : e\}

Q=[g,e,b]

Découverts=[g,e,b]

Fermés=[]
         \end{frame}
         
         
          \begin{frame}
     \frametitle{Déroulement}
     \begin{tikzpicture}[>=triangle 45]
\path
(0,1) node[draw,fill,gray!20](a){\color{white}{$a$}}
(1,2) node[draw,fill,gray!20](b){\color{white}{$b$}}
(1,0) node[draw ](c){$c$}
(2,1) node[draw](d){$d$}
(3,2) node[draw,fill,gray!20](e){\color{white}{$e$}}
(5,2) node[draw](f){$f$}
(4,1) node[draw,fill,gray!20](g){\color{white}{$g$}}
(3,0) node[draw](h){$h$};
\draw[<-]  (a)--(b); \draw  (a)--(c); 
\draw  (b)--(d); \draw[<-]  (b)--(e); 
\draw  (d)--(c); \draw  (d)--(e); 
\draw  (e)--(f); \draw  (f)--(g); 
\draw  (g)--(h); \draw[<-] (e)--(g); 
\end{tikzpicture}
u=b, R=[a,d],v=a,

P=\{ g: None, e : g,b : e, a:b\}

Q=[g,e,b,a]


Découverts=[g,e,b,a]

Fermés=[]
         \end{frame}
         
         
          \begin{frame}
     \frametitle{Déroulement}
     \begin{tikzpicture}[>=triangle 45]
\path
(0,1) node[draw,fill,gray!20](a){\color{white}{$a$}}
(1,2) node[draw,fill,gray!20](b){\color{white}{$b$}}
(1,0) node[draw,fill,gray!20 ](c){\color{white}{$c$}}
(2,1) node[draw](d){$d$}
(3,2) node[draw,fill,gray!20](e){\color{white}{$e$}}
(5,2) node[draw](f){$f$}
(4,1) node[draw,fill,gray!20](g){\color{white}{$g$}}
(3,0) node[draw](h){$h$};
\draw[<-]  (a)--(b); \draw[->]  (a)--(c); 
\draw  (b)--(d); \draw[<-]  (b)--(e); 
\draw  (d)--(c); \draw  (d)--(e); 
\draw  (e)--(f); \draw  (f)--(g); 
\draw  (g)--(h); \draw[<-]  (e)--(g); 
\end{tikzpicture}
u=a, R=[c],v=c,

P=\{ g: None, e : g,b : e, a:b,c:a\}

Q=[g,e,b,a,c]


Découverts=[g,e,b,a,c]

Fermés=[]
         \end{frame}
         
          \begin{frame}
     \frametitle{Déroulement}
     \begin{tikzpicture}[>=triangle 45]
\path
(0,1) node[draw,fill,gray!20](a){\color{white}{$a$}}
(1,2) node[draw,fill,gray!20](b){\color{white}{$b$}}
(1,0) node[draw,fill,gray!20 ](c){\color{white}{$c$}}
(2,1) node[draw,fill,gray!20](d){\color{white}{$d$}}
(3,2) node[draw,fill,gray!20](e){\color{white}{$e$}}
(5,2) node[draw](f){$f$}
(4,1) node[draw,fill,gray!20](g){\color{white}{$g$}}
(3,0) node[draw](h){$h$};
\draw[<-]  (a)--(b); \draw[->]  (a)--(c); 
\draw  (b)--(d); \draw[<-]  (b)--(e); 
\draw[<-]  (d)--(c); \draw  (d)--(e); 
\draw  (e)--(f); \draw  (f)--(g); 
\draw  (g)--(h); \draw[<-]  (e)--(g); 
\end{tikzpicture}
u=c, R=[d],v=d,

P=\{ g: None, e : g,b : e, a:b,c:a, d:c\}

Q=[g,e,b,a,c,d]


Découverts=[g,e,b,a,c,d]

Fermés=[]
         \end{frame}
         
          \begin{frame}
     \frametitle{Déroulement}
     \begin{tikzpicture}[>=triangle 45]
\path
(0,1) node[draw,fill,gray!20](a){\color{white}{$a$}}
(1,2) node[draw,fill,gray!20](b){\color{white}{$b$}}
(1,0) node[draw,fill,gray!20 ](c){\color{white}{$c$}}
(2,1) node[draw,fill,black,circle](d){\color{white}{$d$}}
(3,2) node[draw,fill,gray!20](e){\color{white}{$e$}}
(5,2) node[draw](f){$f$}
(4,1) node[draw,fill,gray!20](g){\color{white}{$g$}}
(3,0) node[draw](h){$h$};
\draw[<-]  (a)--(b); \draw[->]  (a)--(c); 
\draw  (b)--(d); \draw[<-]  (b)--(e); 
\draw[<-]  (d)--(c); \draw  (d)--(e); 
\draw  (e)--(f); \draw  (f)--(g); 
\draw  (g)--(h); \draw[<-]  (e)--(g); 
\end{tikzpicture}
u=d, R=[], 

P=\{ g: None, e : g,b : e, a:b,c:a, d:c\}

Q=[g,e,b,a,c]


Découverts=[g,e,b,a,c,d]

Fermés=[d]
         \end{frame}
         
          \begin{frame}
     \frametitle{Déroulement}
     \begin{tikzpicture}[>=triangle 45]
\path
(0,1) node[draw,fill,gray!20](a){\color{white}{$a$}}
(1,2) node[draw,fill,gray!20](b){\color{white}{$b$}}
(1,0) node[draw,fill,black,circle ](c){\color{white}{$c$}}
(2,1) node[draw,fill,black,circle](d){\color{white}{$d$}}
(3,2) node[draw,fill,gray!20](e){\color{white}{$e$}}
(5,2) node[draw](f){$f$}
(4,1) node[draw,fill,gray!20](g){\color{white}{$g$}}
(3,0) node[draw](h){$h$};
\draw[<-]  (a)--(b); \draw[->]  (a)--(c); 
\draw  (b)--(d); \draw[<-]  (b)--(e); 
\draw[<-]  (d)--(c); \draw  (d)--(e); 
\draw  (e)--(f); \draw  (f)--(g); 
\draw  (g)--(h); \draw[<-]  (e)--(g); 
\end{tikzpicture}
u=c, R=[], 


P=\{ g: None, e : g,b : e, a:b,c:a, d:c\}

Q=[g,e,b,a]

Découverts=[g,e,b,a,c,d]

Fermés=[d,c]
         \end{frame}
         
          \begin{frame}
     \frametitle{Déroulement}
     \begin{tikzpicture}[>=triangle 45]
\path
(0,1) node[draw,fill,black,circle](a){\color{white}{$a$}}
(1,2) node[draw,fill,gray!20](b){\color{white}{$b$}}
(1,0) node[draw,fill,black,circle ](c){\color{white}{$c$}}
(2,1) node[draw,fill,black,circle](d){\color{white}{$d$}}
(3,2) node[draw,fill,gray!20](e){\color{white}{$e$}}
(5,2) node[draw](f){$f$}
(4,1) node[draw,fill,gray!20](g){\color{white}{$g$}}
(3,0) node[draw](h){$h$};
\draw[<-]  (a)--(b); \draw[->]  (a)--(c); 
\draw  (b)--(d); \draw[<-]  (b)--(e); 
\draw[<-]  (d)--(c); \draw  (d)--(e); 
\draw  (e)--(f); \draw  (f)--(g); 
\draw  (g)--(h); \draw[<-]  (e)--(g); 
\end{tikzpicture}
u=a, R=[], 

P=\{ g: None, e : g,b : e, a:b,c:a, d:c\}

Q=[g,e,b]


Découverts=[g,e,b,a,c,d]

Fermés=[d,c,a]
 
         \end{frame}
         
          \begin{frame}
     \frametitle{Déroulement}
     \begin{tikzpicture}[>=triangle 45]
\path
(0,1) node[draw,fill,black,circle](a){\color{white}{$a$}}
(1,2) node[draw,fill,black,circle](b){\color{white}{$b$}}
(1,0) node[draw,fill,black,circle ](c){\color{white}{$c$}}
(2,1) node[draw,fill,black,circle](d){\color{white}{$d$}}
(3,2) node[draw,fill,gray!20](e){\color{white}{$e$}}
(5,2) node[draw](f){$f$}
(4,1) node[draw,fill,gray!20](g){\color{white}{$g$}}
(3,0) node[draw](h){$h$};
\draw[<-]  (a)--(b); \draw[->]  (a)--(c); 
\draw  (b)--(d); \draw[<-]  (b)--(e); 
\draw[<-]  (d)--(c); \draw  (d)--(e); 
\draw  (e)--(f); \draw  (f)--(g); 
\draw  (g)--(h); \draw[<-]  (e)--(g); 
\end{tikzpicture}
u=b, R=[], 

P=\{ g: None, e : g,b : e, a:b,c:a, d:c\}

Q=[g,e]


Découverts=[g,e,b,a,c,d]

Fermés=[d,c,a,b]
         \end{frame}
         
          \begin{frame}
     \frametitle{Déroulement}
     \begin{tikzpicture}[>=triangle 45]
\path
(0,1) node[draw,fill,black,circle](a){\color{white}{$a$}}
(1,2) node[draw,fill,black,circle](b){\color{white}{$b$}}
(1,0) node[draw,fill,black,circle ](c){\color{white}{$c$}}
(2,1) node[draw,fill,black,circle](d){\color{white}{$d$}}
(3,2) node[draw,fill,gray!20](e){\color{white}{$e$}}
(5,2) node[draw,fill,gray!20](f){\color{white}{$f$}}
(4,1) node[draw,fill,gray!20](g){\color{white}{$g$}}
(3,0) node[draw](h){$h$};
\draw[<-]  (a)--(b); \draw[->]  (a)--(c); 
\draw  (b)--(d); \draw[<-]  (b)--(e); 
\draw[<-]  (d)--(c); \draw  (d)--(e); 
\draw[->]   (e)--(f); \draw  (f)--(g); 
\draw  (g)--(h); \draw[<-]  (e)--(g); 
\end{tikzpicture}
u=e, R=[f], v=f,

P=\{ g: None, e : g,b : e, a:b,c:a, d:c,f:e\}

Q=[g,e,f]


Découverts=[g,e,b,a,c,d,f]

Fermés=[d,c,a,b]

         \end{frame}
         
          \begin{frame}
     \frametitle{Déroulement}
     \begin{tikzpicture}[>=triangle 45]
\path
(0,1) node[draw,fill,black,circle](a){\color{white}{$a$}}
(1,2) node[draw,fill,black,circle](b){\color{white}{$b$}}
(1,0) node[draw,fill,black,circle ](c){\color{white}{$c$}}
(2,1) node[draw,fill,black,circle](d){\color{white}{$d$}}
(3,2) node[draw,fill,gray!20](e){\color{white}{$e$}}
(5,2) node[draw,fill,black,circle](f){\color{white}{$f$}}
(4,1) node[draw,fill,gray!20](g){\color{white}{$g$}}
(3,0) node[draw](h){$h$};
\draw[<-]  (a)--(b); \draw[->]  (a)--(c); 
\draw  (b)--(d); \draw[<-]  (b)--(e); 
\draw[<-]  (d)--(c); \draw  (d)--(e); 
\draw[->]   (e)--(f); \draw  (f)--(g); 
\draw  (g)--(h); \draw[<-]  (e)--(g); 
\end{tikzpicture}
u=f, R=[],  

P=\{ g: None, e : g,b : e, a:b,c:a, d:c,f:e\}

Q=[g,e]



Découverts=[g,e,b,a,c,d,f]

Fermés=[d,c,a,b,f]

         \end{frame}
         
          \begin{frame}
     \frametitle{Déroulement}
      \begin{tikzpicture}[>=triangle 45]
\path
(0,1) node[draw,fill,black,circle](a){\color{white}{$a$}}
(1,2) node[draw,fill,black,circle](b){\color{white}{$b$}}
(1,0) node[draw,fill,black,circle ](c){\color{white}{$c$}}
(2,1) node[draw,fill,black,circle](d){\color{white}{$d$}}
(3,2) node[draw,fill,black,circle](e){\color{white}{$e$}}
(5,2) node[draw,fill,black,circle](f){\color{white}{$f$}}
(4,1) node[draw,fill,gray!20](g){\color{white}{$g$}}
(3,0) node[draw](h){$h$};
\draw[<-]  (a)--(b); \draw[->]  (a)--(c); 
\draw  (b)--(d); \draw[<-]  (b)--(e); 
\draw[<-]  (d)--(c); \draw  (d)--(e); 
\draw[->]   (e)--(f); \draw  (f)--(g); 
\draw  (g)--(h); \draw[<-]  (e)--(g); 
\end{tikzpicture}
u=e, R=[],  

P=\{ g: None, e : g,b : e, a:b,c:a, d:c,f:e\}

Q=[g]


Découverts=[g,e,b,a,c,d,f]

Fermés=[d,c,a,b,f,e]

         \end{frame}
         
          \begin{frame}
     \frametitle{Déroulement}
      \begin{tikzpicture}[>=triangle 45]
\path
(0,1) node[draw,fill,black,circle](a){\color{white}{$a$}}
(1,2) node[draw,fill,black,circle](b){\color{white}{$b$}}
(1,0) node[draw,fill,black,circle ](c){\color{white}{$c$}}
(2,1) node[draw,fill,black,circle](d){\color{white}{$d$}}
(3,2) node[draw,fill,black,circle](e){\color{white}{$e$}}
(5,2) node[draw,fill,black,circle](f){\color{white}{$f$}}
(4,1) node[draw,fill,gray!20](g){\color{white}{$g$}}
(3,0) node[draw,fill,gray!20](h){\color{white}{$h$}};
\draw[<-]  (a)--(b); \draw[->]  (a)--(c); 
\draw  (b)--(d); \draw[<-]  (b)--(e); 
\draw[<-]  (d)--(c); \draw  (d)--(e); 
\draw[->]   (e)--(f); \draw  (f)--(g); 
\draw[->]  (g)--(h); \draw[<-]  (e)--(g); 
\end{tikzpicture}
u=g, R=[h],  v=h,

P=\{ g: None, e : g,b : e, a:b,c:a, d:c,f:e,h:g\}

Q=[g,h]


Découverts=[g,e,b,a,c,d,f,h]

Fermés=[d,c,a,b,f,e]

         \end{frame}
         
         
          \begin{frame}
     \frametitle{Déroulement}
     \begin{tikzpicture}[>=triangle 45]
\path
(0,1) node[draw,fill,black,circle](a){\color{white}{$a$}}
(1,2) node[draw,fill,black,circle](b){\color{white}{$b$}}
(1,0) node[draw,fill,black,circle ](c){\color{white}{$c$}}
(2,1) node[draw,fill,black,circle](d){\color{white}{$d$}}
(3,2) node[draw,fill,black,circle](e){\color{white}{$e$}}
(5,2) node[draw,fill,black,circle](f){\color{white}{$f$}}
(4,1) node[draw,fill,gray!20](g){\color{white}{$g$}}
(3,0) node[draw,fill,black,circle](h){\color{white}{$h$}};
\draw[<-]  (a)--(b); \draw[->]  (a)--(c); 
\draw  (b)--(d); \draw[<-]  (b)--(e); 
\draw[<-]  (d)--(c); \draw  (d)--(e); 
\draw[->]   (e)--(f); \draw  (f)--(g); 
\draw[->]  (g)--(h); \draw[<-]  (e)--(g); 
\end{tikzpicture}
u=h, R=[],   

P=\{ g: None, e : g,b : e, a:b,c:a, d:c,f:e,h:g\}

Q=[g]


Découverts=[g,e,b,a,c,d,f,h]

Fermés=[d,c,a,b,f,e,h]
         \end{frame}
         
          \begin{frame}
     \frametitle{Déroulement}
     \begin{tikzpicture}[>=triangle 45]
\path
(0,1) node[draw,fill,black,circle](a){\color{white}{$a$}}
(1,2) node[draw,fill,black,circle](b){\color{white}{$b$}}
(1,0) node[draw,fill,black,circle ](c){\color{white}{$c$}}
(2,1) node[draw,fill,black,circle](d){\color{white}{$d$}}
(3,2) node[draw,fill,black,circle](e){\color{white}{$e$}}
(5,2) node[draw,fill,black,circle](f){\color{white}{$f$}}
(4,1) node[draw,fill,black,circle](g){\color{white}{$g$}}
(3,0) node[draw,fill,black,circle](h){\color{white}{$h$}};
\draw[<-]  (a)--(b); \draw[->]  (a)--(c); 
\draw  (b)--(d); \draw[<-]  (b)--(e); 
\draw[<-]  (d)--(c); \draw  (d)--(e); 
\draw[->]   (e)--(f); \draw  (f)--(g); 
\draw[->]  (g)--(h); \draw[<-]  (e)--(g); 
\end{tikzpicture}
u=g, R=[],   

P=\{ g: None, e : g,b : e, a:b,c:a, d:c,f:e,h:g\}

Q=[ ]



Découverts=[g,e,b,a,c,d,f,h]

Fermés=[d,c,a,b,f,e,h,g]
         \end{frame}
         
         
\begin{frame}
 \frametitle{Arborescence associée au parcours}
 
 \begin{tikzpicture}[>=triangle 45,x=1.5cm,y=1.3cm]
\path
(-0.6,-3) node[draw,fill,black,circle](a){\color{white}{$a$}}
(-0.4,-2) node[draw,fill,black,circle](b){\color{white}{$b$}}
(-0.8,-4) node[draw,fill,black,circle ](c){\color{white}{$c$}}
(-1,-5) node[draw,fill,black,circle](d){\color{white}{$d$}}
(-0.2,-1) node[draw,fill,black,circle](e){\color{white}{$e$}}
(1,-2) node[draw,fill,black,circle](f){\color{white}{$f$}}
(0,0) node[draw,fill,black,circle](g){\color{white}{$g$}}
(2,-1) node[draw,fill,black,circle](h){\color{white}{$h$}};
\draw[<-]  (a)--(b); \draw[->]  (a)--(c); 
\draw[dashed]  (b)to[bend left](d); \draw[<-]  (b)--(e); 
\draw[<-]  (d)--(c); \draw[dashed]  (d)to[bend left](e); 
\draw[->]   (e)--(f); \draw[dashed]  (f)--(g); 
\draw[->]  (g)--(h); \draw[<-]  (e)--(g); 
\end{tikzpicture}

\end{frame}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%% CORRIGE EX 3
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{resolution}


      \begin{frame}
     \frametitle{DFS : une programmation en  python}
     
     \begin{minipage}{9cm}
 \scalebox{0.7}{
\begin{codepython}
def dfs(G,s):
    
\hp    couleur=dict()
    
\hp     for v in G:couleur[v]='blanc'
    
 \hp      P=dict()
 
  \hp   P[s]=None 
    
\hp     couleur[s]='gris'

\hp     Q=[s]
    
  \hp   while Q:
       
   \hp \hp      u=Q[-1]
       
   \hp \hp      R=[y for y in G[u] if couleur[y]=='blanc']
        
   \hp \hp      if R: 
        
    \hp \hp \hp         v=R[0]
            
    \hp \hp \hp         couleur[v]='gris'
            
    \hp \hp \hp         P[v]=u
            
    \hp \hp \hp         Q.append(v)
            
    \hp \hp     else : 
            
     \hp \hp \hp        Q.pop()  
            
    \hp \hp \hp         couleur[u]='noir'
            
 \hp    return P
\end{codepython}
}
\end{minipage}
 \begin{minipage}{2cm}
           \href{run:python/dfs.py}{\beamerbutton{DFS  en python}}
\end{minipage}
       
         \end{frame}    
         
         
\begin{frame}
 \frametitle{La même programmation, moins colorée}
 
  
\begin{codepython}
def dfs(G,s):

\hp    P,Q=\{s:None\},[s]
    
 \hp     while Q:
    
 \hp  \hp         u=Q[-1]
        
 \hp  \hp         R=[y for y in G[u] if y not in P]
        
 \hp  \hp         if R:
        
 \hp  \hp  \hp             v=random.choice(R)
            
  \hp  \hp  \hp            P[v]=u
            
 \hp  \hp  \hp             Q.append(v)
            
  \hp  \hp        else :
        
    \hp  \hp  \hp          Q.pop()
            
  \hp    return P
\end{codepython}
 
\end{frame}

\end{resolution}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%% FIN  CORRIGE EX 3
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

 
\begin{frame}
 \frametitle{tri topologique}
 \textbf{Exemple d'application du parcours en profondeur.}
 
 
 Début d'année,  vos enseignants préparent le cours d'ISN. 
 
 Pour cela, ils  découpent les notions en chapitres a, b, c, d\dots  
 
 Sur le graphe ci-dessous, une flèche du chapitre x vers le chapitre y signifie que x doit être traité avant y.
 
 \scalebox{0.5}{
 \begin{tikzpicture}[>=triangle 45]
\path
(3,0) node[draw](a){$a$}
(5,0) node[draw](b){$b$}
(10,0) node[draw](c){$c$}
(11,4) node[draw](d){$d$}
(8,4) node[draw](e){$e$}
(8,2) node[draw](f){$f$}
(1,1) node[draw](g){$g$}
(4,4) node[draw ](h){$h$}
(4,6) node[draw ](i){$i$}
(5,2) node[draw ](j){$j$}
(9,2) node[draw ](k){$k$};
\draw[->] (a)--(b.220);
\draw[->] (a)--(g);\draw[->] (b)--(c);
\draw[->] (b)--(g.30);
\draw[->] (c)--(d.275);
\draw[->] (e)--(d.180);
\draw[->] (f)--(c);\draw[->] (f)--(e);
\draw[->] (h)--(g);\draw[->] (i)--(h);
\draw[->] (i)--(d.110);\draw[->] (j)--(b);\draw[->] (j)--(f);
\draw[->] (k)--(e);\draw[->] (k)--(d.240);
\end{tikzpicture}
}

Pour une meilleure organisation et savoir où commencer , on aimerait réorganiser la représentation du graphe de façon à ce que tous les sommets soient dessinés alignés, toutes les flèches du schéma devant être orientées vers la droite.


\end{frame}






\begin{frame}
 \frametitle{tri topologique}
 L'énumération des sommets du graphe en ordre inverse de leur date de fermeture dans l'algorithme de parcours en profondeur permet d'obtenir un ordre des sommets satisfaisant la demande.
 
\begin{minipage}{8cm}
\scalebox{0.6}{
\begin{codepython}
\textcolor{blue}{def} lancement(G):

\hp    for s in G:
    
 \hp   \hp          if couleur[s]=='blanc' : parcours(G,s)

\textcolor{blue}{def} parcours(G,s):   

 \hp      couleur[s]='gris'
    
\hp       for v in G[s]:
    
 \hp   \hp          if couleur[v]=='blanc' : parcours(G,v)
            
\hp       P.append(s)
          
 \textcolor{red}{\# \# \# \# \# \#}
 
couleur=dict()

for v in G:couleur[v]='blanc'

P=list() 

lancement(G)

P.reverse()

print P

\end{codepython}
}
\end{minipage}
\begin{minipage}{3cm}
     \href{run:tritopo/tritopo.py}{\beamerbutton{tri topo python}}
\end{minipage}

\end{frame}


 
  
 
\end{document}

