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


   

  
 \begin{frame}
  \frametitle{Exercices à rendre}
  
 Trois exercices sont à rendre.
 \begin{itemize}
  \item L' exercice 1  pourra être rendu sur papier mardi 2 avril (ou en version électronique si vous préférez).
  \item Les exercices 2 et 3 sont à rendre dans  les casiers numériques de vos enseignants lundi 1 avril.
 \end{itemize}

 \end{frame}
    
    
   
 \begin{frame}
  \frametitle{A savoir}
  
 A la suite de cette séance, vous devrez \textbf{savoir} parcourir un graphe en profondeur et en largeur.

 \end{frame}
    
    
     \begin{frame}
    \frametitle{L'essentiel de la notion de graphe}
 On peut appréhender la notion de graphe par l'une de ses représentations classiques : des points (sommets du graphe) et des courbes reliant certains  de ces points (arêtes du graphe).

\begin{tikzpicture}[scale=0.8]
\path
(1,1) node[draw](g){$g$}
(3,0) node[draw](a){$a$}
(4,4) node[draw ](h){$h$}
(5,0) node[draw](b){$b$}
(11,0) node[draw](c){$c$}
(12,4) node[draw](d){$d$}
(8,4) node[draw](e){$e$}
(8,2) node[draw](f){$f$};
\draw (h)--node[sloped,above]{$1$}(g);
\draw (h)--node[sloped,above]{$2$}(a);
\draw (a)--node[sloped,above]{$3$}(g);
\draw (h)--node[sloped,above]{$4$}(e);
\draw (h)--node[sloped,above]{$5$}(b);
\draw (e)--node[sloped,above]{$6$}(f);
\draw (b)--node[sloped,above]{$7$}(f);
\draw (b)--node[sloped,above]{$8$}(c);
\draw (f)--node[sloped,above]{$9$}(c);
\draw (e)--node[sloped,above]{$10$}(c);
\draw (e)--node[sloped,above]{$11$}(d);
\draw (d)--node[sloped,above]{$12$}(c);
\end{tikzpicture}

\only<1>{Les sommets de ce graphe sont $a$, $b$, $c$, $d$, $e$, $f$, $g$, $h$.
Les sommets $e$ et $c$ sont adjacents (voisins) : ils sont en effet reliés par l'arête 10.
Le sommet $b$ a pour voisins $h$, $f$ et $c$.
Le sommet $a$ est incident aux arêtes 2 et 3.}

 
\only<2>{Lorsqu'on passe d'un sommet à un autre en se déplaçant le long d'arêtes et de sommets, on dit que l'on définit un chemin dans le graphe.
On peut par exemple définir le chemin g, 3, a, 2, h, 5, b, 7, f dans le graphe ci-dessus.   }
    \end{frame}

  
 \begin{frame}
  \frametitle{Exemples de situations modélisées par un graphe}
  
 
    \begin{itemize}
     \item<2-> Le web : chaque page est un sommet du graphe, chaque lien hypertexte est une arête entre deux sommets.
     \item<3-> Un réseau ferroviaire : chaque gare est un sommet, les voies entre deux gares sont les arêtes. Idem avec un réseau routier.
     \item<4-> Un réseau social : les sommets sont les personnes, deux personnes sont adjacentes dans ce graphe lorsqu'elles sont ``amies''. 
     
     {\small{Si la notion d'amitié n'est pas réciproque, le graphe est orienté.}}
    \end{itemize}
    
    \only<5>{La structure de graphe est en science de l'informatique une structure abstraite omniprésente.}
 \end{frame}
 
 
\begin{frame}
  \frametitle{Représentation informatique d'un graphe}
  
  Une structure théorique comme un graphe est susceptible de nombreuses implémentations, selon le type de problèmes à résoudre.
  
  \vspace{3mm}
  
  \pause
  
  
  On peut par exemple utiliser la matrice d'adjacence du graphe.
  
  \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}
\begin{minipage}{5cm}
\scalebox{0.7}{
$ \phantom{Mat=}\bordermatrix{
&a&b&c&d&e&f&g&h\cr
a&0 & 1 & 1 &0&0&0&0&0\cr
b&1 & 0 & 0&1&1&0&0&0\cr
c&1&0&0&1&0&0&0&0\cr
d&0&1&1&0&1&0&0&0\cr
e&0&1&0&1&0&1&1&0\cr
f&0&0&0&0&1&0&1&0\cr
g&0&0&0&0&1&1&0&1\cr
h&0&0&0&0&0&0&1&0}$
}
\end{minipage}
  \end{frame}
  
  
  \begin{frame}
   \frametitle{Exemple de codage : utilisation d'un  dictionnaire python}
   
    
 
 

\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}
  
  
  
  
  
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  %%%%%%%%%%%%% NOTION DE FILE %%%%%%%%%%%%%%%%%%%
  %%%%%%%%%%%%% NOTION DE PILE%%%%%%%%%%%%%
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  

\begin{frame}
\frametitle{PILE et FILE}

Les notions de   \textsc{pile} et de \textsc{file} sont deux structures de données abstraites importantes en informatique.

On limite ci-dessous la présentation de ces notions aux besoins des parcours de graphes envisagés ci-après.
   
\end{frame}


\begin{frame}
\frametitle{PILE  (stack) }

La structure de \textsc{pile} est celle d'une pile d'assiettes :

\begin{itemize}
 \item Pour ranger les assiettes, on les  empile  les unes sur les autres.
 \item Lorsqu'on veut utiliser une assiette, c'est l'assiette qui a été empilée en dernier qui est utilisée.
\end{itemize}

Structure LIFO  (last in, first out)

   
\end{frame}



\begin{frame}
\frametitle{FILE  (queue) }

La structure de \textsc{file} est celle d'une file d'attente à un guichet :

\begin{itemize}
 \item  Les nouvelles personnes qui arrivent se rangent à la fin de la file d'attente.
 \item La personne servie est celle qui est arrivée en premier dans la file.
\end{itemize}

Structure FIFO  (first in, first out).

   
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
%%%%%%%%%%%%%%  PARCOURS EN LARGEUR
 
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%

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



  \begin{frame}
   \frametitle{Parcours en largeur : 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 largeur, on utilise une file. On enfile le sommet de départ (on visite la page index du site).
   \item<3-> On visite les voisins de la tête de file (pages ciblées par la page de tête de file). On les enfile (en les numérotant au fur et à mesure de leur découverte) s'ils ne sont pas déjà présents dans la file, ni déjà passés dans la file.
   \item<4-> On défile (c'est à dire : on supprime la tête de file). 
   \item<5-> On recommence au point 2 (tant que c'est possible, c'est à dire tant que la file n'est pas vide).
  \end{enumerate}
\only<6>{En d'autres termes, on traite  toujours en priorité les  liens des pages le plus tôt découvertes.  }
\end{frame}
     
    
  
  
  \begin{frame}
   \frametitle{Parcours en largeur d'un arbre}
   Parcourir en largeur 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{s}
child{node{}child{node{}}child{node{}child{node{}}child{node{}}}}
child{node{}child{node{}}child{node{}}child{node{}}}
child{node{}child{node{}child{node{}}child{node{}}}};
    \end{tikzpicture}
    }
 \end{frame}
 
 
 \begin{frame}
   \frametitle{Parcours en largeur 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!20]{\textcolor{white}{1}}
child{node{}child{node{}}child{node{}child{node{}}child{node{}}}}
child{node{}child{node{}}child{node{}}child{node{}}}
child{node{}child{node{}child{node{}}child{node{}}}};
    \end{tikzpicture}
    }
 \end{frame}
 
 \begin{frame}
   \frametitle{Parcours en largeur 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=gray!20]{\textcolor{white}{2}}child{node{\textcolor{white}{5 }}}child{node{\textcolor{white}{6}}child{node{\textcolor{white}{11}}}child{node{\textcolor{white}{12}}}}}
child{node[fill,color=gray!20]{\textcolor{white}{3}}child{node{\textcolor{white}{7}}}child{node{\textcolor{white}{8}}}child{node{\textcolor{white}{9}}}}
child{node[fill,color=gray!20]{\textcolor{white}{\textcolor{white}{4}}}child{node{\textcolor{white}{10}}child{node{\textcolor{white}{13}}}child{node{\textcolor{white}{14}}}}};
    \end{tikzpicture}
    }
    
    Enfiler : passage en gris.     
    Défiler : passage en noir.
    
    L'ordre pour enfiler les voisins (ni gris, ni noirs) dépend de l'implantation. 
 \end{frame}

  
 
 \begin{frame}
   \frametitle{Parcours en largeur 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=gray!20]{\textcolor{white}{5 }}}child{node[fill,color=gray!20]{\textcolor{white}{6}}child{node{\textcolor{white}{11}}}child{node{\textcolor{white}{12}}}}}
child{node[fill,color=gray!20]{\textcolor{white}{3}}child{node{\textcolor{white}{7}}}child{node{\textcolor{white}{8}}}child{node{\textcolor{white}{9}}}}
child{node[fill,color=gray!20]{\textcolor{white}{\textcolor{white}{4}}}child{node{\textcolor{white}{10}}child{node{\textcolor{white}{13}}}child{node{\textcolor{white}{14}}}}};
    \end{tikzpicture}
    }
 \end{frame}
 
 
 
 
 \begin{frame}
   \frametitle{Parcours en largeur 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=gray!20]{\textcolor{white}{5 }}}child{node[fill,color=gray!20]{\textcolor{white}{6}}child{node{\textcolor{white}{11}}}child{node{\textcolor{white}{12}}}}}
child{node[fill,color=black]{\textcolor{white}{3}}child{node[fill,color=gray!20]{\textcolor{white}{7}}}child{node[fill,color=gray!20]{\textcolor{white}{8}}}child{node[fill,color=gray!20]{\textcolor{white}{9}}}}
child{node[fill,color=gray!20]{\textcolor{white}{\textcolor{white}{4}}}child{node{\textcolor{white}{10}}child{node{\textcolor{white}{13}}}child{node{\textcolor{white}{14}}}}};
    \end{tikzpicture}
    }
 \end{frame}
 
 
 
 
 \begin{frame}
   \frametitle{Parcours en largeur 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=gray!20]{\textcolor{white}{5 }}}child{node[fill,color=gray!20]{\textcolor{white}{6}}child{node{\textcolor{white}{11}}}child{node{\textcolor{white}{12}}}}}
child{node[fill,color=black]{\textcolor{white}{3}}child{node[fill,color=gray!20]{\textcolor{white}{7}}}child{node[fill,color=gray!20]{\textcolor{white}{8}}}child{node[fill,color=gray!20]{\textcolor{white}{9}}}}
child{node[fill,color=black]{ \textcolor{white}{4}}child{node[fill,color=gray!20]{\textcolor{white}{10}}child{node{\textcolor{white}{13}}}child{node{\textcolor{white}{14}}}}};
    \end{tikzpicture}
    }
 \end{frame}
 
 
 
 
 
 
 
 \begin{frame}
   \frametitle{Parcours en largeur 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}{5 }}}child{node[fill,color=gray!20]{\textcolor{white}{6}}child{node{\textcolor{white}{11}}}child{node{\textcolor{white}{12}}}}}
child{node[fill,color=black]{\textcolor{white}{3}}child{node[fill,color=gray!20]{\textcolor{white}{7}}}child{node[fill,color=gray!20]{\textcolor{white}{8}}}child{node[fill,color=gray!20]{\textcolor{white}{9}}}}
child{node[fill,color=black]{ \textcolor{white}{4}}child{node[fill,color=gray!20]{\textcolor{white}{10}}child{node{\textcolor{white}{13}}}child{node{\textcolor{white}{14}}}}};
    \end{tikzpicture}
    }
 \end{frame}
 
 
 
 \begin{frame}
   \frametitle{Parcours en largeur 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}{5 }}}child{node[fill,color=black]{\textcolor{white}{6}}child{node[fill,color=gray!20]{\textcolor{white}{11}}}child{node[fill,color=gray!20]{\textcolor{white}{12}}}}}
child{node[fill,color=black]{\textcolor{white}{3}}child{node[fill,color=gray!20]{\textcolor{white}{7}}}child{node[fill,color=gray!20]{\textcolor{white}{8}}}child{node[fill,color=gray!20]{\textcolor{white}{9}}}}
child{node[fill,color=black]{ \textcolor{white}{4}}child{node[fill,color=gray!20]{\textcolor{white}{10}}child{node{\textcolor{white}{13}}}child{node{\textcolor{white}{14}}}}};
    \end{tikzpicture}
    }
 \end{frame}
 
 
 
 \begin{frame}
   \frametitle{Parcours en largeur 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}{5 }}}child{node[fill,color=black]{\textcolor{white}{6}}child{node[fill,color=gray!20]{\textcolor{white}{11}}}child{node[fill,color=gray!20]{\textcolor{white}{12}}}}}
child{node[fill,color=black]{\textcolor{white}{3}}child{node[fill,color=black]{\textcolor{white}{7}}}child{node[fill,color=gray!20]{\textcolor{white}{8}}}child{node[fill,color=gray!20]{\textcolor{white}{9}}}}
child{node[fill,color=black]{ \textcolor{white}{4}}child{node[fill,color=gray!20]{\textcolor{white}{10}}child{node{\textcolor{white}{13}}}child{node{\textcolor{white}{14}}}}};
    \end{tikzpicture}
    }
 \end{frame}
 
 
 
 
 
 \begin{frame}
   \frametitle{Parcours en largeur 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}{5 }}}child{node[fill,color=black]{\textcolor{white}{6}}child{node[fill,color=gray!20]{\textcolor{white}{11}}}child{node[fill,color=gray!20]{\textcolor{white}{12}}}}}
child{node[fill,color=black]{\textcolor{white}{3}}child{node[fill,color=black]{\textcolor{white}{7}}}child{node[fill,color=black]{\textcolor{white}{8}}}child{node[fill,color=gray!20]{\textcolor{white}{9}}}}
child{node[fill,color=black]{ \textcolor{white}{4}}child{node[fill,color=gray!20]{\textcolor{white}{10}}child{node{\textcolor{white}{13}}}child{node{\textcolor{white}{14}}}}};
    \end{tikzpicture}
    }
 \end{frame}
 
 
 
 
 \begin{frame}
   \frametitle{Parcours en largeur 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}{5 }}}child{node[fill,color=black]{\textcolor{white}{6}}child{node[fill,color=gray!20]{\textcolor{white}{11}}}child{node[fill,color=gray!20]{\textcolor{white}{12}}}}}
child{node[fill,color=black]{\textcolor{white}{3}}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}{4}}child{node[fill,color=gray!20]{\textcolor{white}{10}}child{node{\textcolor{white}{13}}}child{node{\textcolor{white}{14}}}}};
    \end{tikzpicture}
    }
 \end{frame}
 
 
 
 \begin{frame}
   \frametitle{Parcours en largeur 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}{5 }}}child{node[fill,color=black]{\textcolor{white}{6}}child{node[fill,color=gray!20]{\textcolor{white}{11}}}child{node[fill,color=gray!20]{\textcolor{white}{12}}}}}
child{node[fill,color=black]{\textcolor{white}{3}}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}{4}}child{node[fill,color=black]{\textcolor{white}{10}}child{node[fill,color=gray!20]{\textcolor{white}{13}}}child{node[fill,color=gray!20]{\textcolor{white}{14}}}}};
    \end{tikzpicture}
    }
 \end{frame}
 
 
 
 \begin{frame}
   \frametitle{Parcours en largeur 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}{5 }}}child{node[fill,color=black]{\textcolor{white}{6}}child{node[fill,color=black]{\textcolor{white}{11}}}child{node[fill,color=gray!20]{\textcolor{white}{12}}}}}
child{node[fill,color=black]{\textcolor{white}{3}}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}{4}}child{node[fill,color=black]{\textcolor{white}{10}}child{node[fill,color=gray!20]{\textcolor{white}{13}}}child{node[fill,color=gray!20]{\textcolor{white}{14}}}}};
    \end{tikzpicture}
    }
 \end{frame}
 
 
 
 
 \begin{frame}
   \frametitle{Parcours en largeur 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}{5 }}}child{node[fill,color=black]{\textcolor{white}{6}}child{node[fill,color=black]{\textcolor{white}{11}}}child{node[fill,color=black]{\textcolor{white}{12}}}}}
child{node[fill,color=black]{\textcolor{white}{3}}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}{4}}child{node[fill,color=black]{\textcolor{white}{10}}child{node[fill,color=gray!20]{\textcolor{white}{13}}}child{node[fill,color=gray!20]{\textcolor{white}{14}}}}};
    \end{tikzpicture}
    }
 \end{frame}
 
 
 
 \begin{frame}
   \frametitle{Parcours en largeur 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}{5 }}}child{node[fill,color=black]{\textcolor{white}{6}}child{node[fill,color=black]{\textcolor{white}{11}}}child{node[fill,color=black]{\textcolor{white}{12}}}}}
child{node[fill,color=black]{\textcolor{white}{3}}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}{4}}child{node[fill,color=black]{\textcolor{white}{10}}child{node[fill,color=black]{\textcolor{white}{13}}}child{node[fill,color=gray!20]{\textcolor{white}{14}}}}};
    \end{tikzpicture}
    }
 \end{frame}
 
 
 
 \begin{frame}
   \frametitle{Parcours en largeur 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}{5 }}}child{node[fill,color=black]{\textcolor{white}{6}}child{node[fill,color=black]{\textcolor{white}{11}}}child{node[fill,color=black]{\textcolor{white}{12}}}}}
child{node[fill,color=black]{\textcolor{white}{3}}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}{4}}child{node[fill,color=black]{\textcolor{white}{10}}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 largeur : une propriété}
    Une façon de comprendre l'algorithme est d'utiliser une notion de distance :
    
    \begin{itemize}
     \item<2-> une page est à distance 1 de la page de départ si on l'atteint par un lien direct depuis la page 1,
     \item<3->  elle est à distance 2 de la page de départ si on peut l'atteindre (par le plus court chemin) en passant par une page  à distance 1 du départ,
     \item<4-> elle est à distance 3 du départ si on peut 
l'atteindre (par le plus court chemin) en passant par une page à distance 1 et une page à distance 2\dots
    \end{itemize}
  \only<5>{L'algorithme de parcours en largeur va visiter en premier lieu toutes les pages à distance 1 du départ, puis toutes les pages à distance 2 du départ, puis toutes les pages à distance 3\dots (c'est en fait cette propriété qui donne son nom à ce type de parcours).}
  \end{frame}
  
  
  \begin{frame}
   \frametitle{BFS (breadth first search) : programmation python}
   \textbf{Exercice avec corrigé.}
   
   Avec la représentation d'un graphe par un dictionnaire comme précédemment, programmer en langage python le BFS avec les variables suivantes :
   
   \begin{itemize}
    \item<2-> 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<3-> Un dictionnaire couleur. Pour tout sommet s, couleur[s] vaut blanc si le sommet s n'est pas passé dans la file, gris s'il est dans la file, noir lorsqu'il est sorti de la file.
    \item<4-> Une liste Q   utilisée comme   file (fifo) : on enfile un sommet lorsqu'il est découvert, on le défile lorsqu'il est terminé (traitement prioritaire des sommets découverts au plus tôt).
   \end{itemize}
  \end{frame}

  
   
  
  \begin{frame}
   \frametitle{Exemple d'exécution}
   
   
   Déroulement attendu du  programme, avec l'appel   bfs(G,'b'),  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,fill,gray!20](b){\color{white}{$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}

P=\{ 'b': None\}

Q=['b']

Découverts (gris ou noirs) =['b']

Fermés (noirs) =[]

   \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,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](g){$g$}
(3,0) node[draw](h){$h$};
\draw[->]  (b)--(a); \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}

P=\{ 'b': None, 'a':'b', 'd':'b', 'e':'b'\}
 
Q=['b','a','d','e']

Découverts =['b','a','d','e']

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,black,circle](b){\color{white}{$b$}}
(1,0) node[draw ](c){$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](g){$g$}
(3,0) node[draw](h){$h$};
\draw[->]  (b)--(a); \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}

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

Q=['a','d','e']

Découverts=['b','a','d','e']

Fermés=['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,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](g){$g$}
(3,0) node[draw](h){$h$};
\draw[->]  (b)--(a); \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}

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

Q=['d','e','c']

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

Fermés=['b','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,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](g){$g$}
(3,0) node[draw](h){$h$};
\draw[->]  (b)--(a); \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}

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

Q=['e','c']

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

Fermés=['b','a','d']
    \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,gray!20 ](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,gray!20](f){\color{white}{$f$}}
(4,1) node[draw,fill,gray!20](g){\color{white}{$g$}}
(3,0) node[draw](h){$h$};
\draw[->]  (b)--(a); \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}

P=\{ 'b': None, 'a':'b', 'd':'b', 'e':'b','c':'a','f':'e','g':'e'\}
 
Q=['c','f','g']

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

Fermés=['b','a','d','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,gray!20](f){\color{white}{$f$}}
(4,1) node[draw,fill,gray!20](g){\color{white}{$g$}}
(3,0) node[draw](h){$h$};
\draw[->]  (b)--(a); \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}

P=\{ 'b': None, 'a':'b', 'd':'b', 'e':'b','c':'a','f':'e','g':'e'\}
 
Q=['f','g']

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

Fermés=['b','a','d','e','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,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[->]  (b)--(a); \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}

P=\{ 'b': None, 'a':'b', 'd':'b', 'e':'b','c':'a','f':'e','g':'e'\}
 
Q=['g']

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

Fermés=['b','a','d','e','c','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,black,circle](g){\color{white}{$g$}}
(3,0) node[draw,fill,gray!20](h){\color{white}{$h$}};
\draw[->]  (b)--(a); \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}

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

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

Fermés=['b','a','d','e','c','f','g']
    \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[->]  (b)--(a); \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}

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

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

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


    \end{frame}
    
    
    
    \begin{frame}
     \frametitle{Arborescence associée au parcours}
     
      \begin{tikzpicture}[>=triangle 45,x=1.5cm,y=1.8cm]
\path
(-1,-1) node[draw,fill,black,circle](a){\color{white}{$a$}}
(0,0) node[draw,fill,black,circle](b){\color{white}{$b$}}
(-2,-2) node[draw,fill,black,circle](c){\color{white}{$c$}}
(0,-1) node[draw,fill,black,circle](d){\color{white}{$d$}}
(1,-1) node[draw,fill,black,circle](e){\color{white}{$e$}}
(0,-2) node[draw,fill,black,circle](f){\color{white}{$f$}}
(2,-2) node[draw,fill,black,circle](g){\color{white}{$g$}}
(2,-3) node[draw,fill,black,circle](h){\color{white}{$h$}};
\draw[->]  (b)--(a); \draw[->]  (a)--(c); 
\draw[->]   (b)--(d); \draw[->]   (b)--(e); 
\draw[dashed]  (d)--(c); \draw[dashed]  (d)--(e); 
\draw[->]  (e)--(f); \draw[dashed]  (f)--(g); 
\draw[->]  (g)--(h); \draw[->]  (e)--(g); 
\end{tikzpicture}

L'ordre de parcours est : ligne après ligne (de la racine vers les feuilles) et de gauche à droite pour une ligne.
    \end{frame}
    
  
  
    
    
    
    
    \begin{frame}
   \frametitle{BFS : un codage en python}
   
\begin{minipage}{7cm}
 \scalebox{0.7}{
\begin{codepython}
def bfs(G,s):

\hp    couleur=dict()
    
\hp       for x in G :  couleur[x]='blanc'
        
 \hp      P=dict()
    
  \hp     P[s]=None  
    
  \hp     couleur[s]='gris'
    
  \hp     Q=[s]
    
  \hp     while Q:
    
  \hp   \hp         u=Q[0] 
        
   \hp   \hp        for v in G[u]: 
        
    \hp   \hp   \hp           if couleur[v]=='blanc':        
            
      \hp   \hp   \hp   \hp             P[v]=u 
                
   \hp   \hp   \hp   \hp                couleur[v]='gris'
                
   \hp   \hp   \hp   \hp                Q.append(v) 
                
 \hp   \hp          Q.pop(0)
        
  \hp   \hp         couleur[u]='noir'
        
\hp       return P
\end{codepython}
}
\end{minipage}
 \begin{minipage}{4cm}
          \href{run:python/bfscouleur.py}{\beamerbutton{BFS en python}}
\end{minipage}
 

  \end{frame}
  
  \begin{frame}
   \frametitle{En ne gardant que l'essentiel}
   
 \begin{codepython}
 
 def bfs(G,s):
 
 \hp   P,Q=\{s:None\},[s]
 
\hp      while Q:

  \hp  \hp        u=Q.pop(0)
  
  \hp  \hp        for v in G[u]:
  
\hp  \hp  \hp  			if v in P : continue

\hp  \hp  \hp  			P[v]=u

\hp  \hp  \hp  			Q.append(v) 

  \hp    return P 
 \end{codepython}
  \end{frame}
  
  
  
  
  \begin{frame}
   \frametitle{Exercice à rendre 1}
   
   
   Vous donnerez, sur papier (ou en version électronique, je vous conseille dans ce cas l'utilisation du logiciel DIA),  un codage python du graphe ci-dessous suivant le modèle précédemment donné  puis le déroulement de     bfs(G,'b') correspondant à ce codage  :
   
 

 
\begin{minipage}{5cm}
\begin{tikzpicture}
\path
(0,0) node[draw](a){$a$}
(0,1) node[draw](b){$b$}
(1,0) node[draw ](c){$c$}
(2,0) node[draw](d){$d$}
(3,0) node[draw](e){$e$}
(2,1) node[draw](f){$f$}
(4,0) node[draw](g){$g$}
(2,-1) node[draw](h){$h$}
(3,-1) node[draw](i){$i$}
(4,-1) node[draw](j){$j$};
\draw  (a)--(b); \draw  (a)--(c); 
\draw  (c)--(d); \draw  (b)--(f); 
\draw  (d)--(f); \draw  (d)--(e); 
\draw  (e)--(g); \draw  (d)--(h); 
\draw  (h)--(i); \draw  (i)--(j); \draw  (i)--(g); 
\end{tikzpicture}
\end{minipage}
  \end{frame}
  
  
  
  \begin{resolution}
   
   
  \begin{frame}
   \frametitle{Exercice à rendre 1 -- Un corrigé}
   
   
    
   
 
\begin{minipage}{5cm}
 \begin{codepython}
G=dict()

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

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

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

G['d']=['c','f','e','h']

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

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

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

G['h']= ['d','i']

G['i']=['g','h', 'j']

G['j']=['i']
\end{codepython} 
\end{minipage} 
\begin{minipage}{5cm}
\begin{tikzpicture}
\path
(0,0) node[draw](a){$a$}
(0,1) node[draw](b){$b$}
(1,0) node[draw ](c){$c$}
(2,0) node[draw](d){$d$}
(3,0) node[draw](e){$e$}
(2,1) node[draw](f){$f$}
(4,0) node[draw](g){$g$}
(2,-1) node[draw](h){$h$}
(3,-1) node[draw](i){$i$}
(4,-1) node[draw](j){$j$};
\draw  (a)--(b); \draw  (a)--(c); 
\draw  (c)--(d); \draw  (b)--(f); 
\draw  (d)--(f); \draw  (d)--(e); 
\draw  (e)--(g); \draw  (d)--(h); 
\draw  (h)--(i); \draw  (i)--(j); \draw  (i)--(g); 
\end{tikzpicture}
\end{minipage}

\end{frame}
  
  
  
\begin{frame}
 \frametitle{Exercice à rendre 1 -- Un corrigé}
   
 \begin{tikzpicture}
\path
(0,0) node[draw](a){$a$}
(0,1) node[draw,fill,gray!20](b){\color{white}{$b$}}
(1,0) node[draw ](c){$c$}
(2,0) node[draw](d){$d$}
(3,0) node[draw](e){$e$}
(2,1) node[draw](f){$f$}
(4,0) node[draw](g){$g$}
(2,-1) node[draw](h){$h$}
(3,-1) node[draw](i){$i$}
(4,-1) node[draw](j){$j$};
\draw  (a)--(b); \draw  (a)--(c); 
\draw  (c)--(d); \draw  (b)--(f); 
\draw  (d)--(f); \draw  (d)--(e); 
\draw  (e)--(g); \draw  (d)--(h); 
\draw  (h)--(i); \draw  (i)--(j); \draw  (i)--(g); 
\end{tikzpicture}

File=[b]
\end{frame}
  
  
  
 
\begin{frame}
 \frametitle{Exercice à rendre 1 -- Un corrigé}
   
 \begin{tikzpicture}
\path
(0,0) node[draw,fill,gray!20](a){\color{white}{$a$}}
(0,1) node[draw,fill,black](b){\color{white}{$b$}}
(1,0) node[draw ](c){$c$}
(2,0) node[draw](d){$d$}
(3,0) node[draw](e){$e$}
(2,1) node[draw,fill,gray!20](f){\color{white}{$f$}}
(4,0) node[draw](g){$g$}
(2,-1) node[draw](h){$h$}
(3,-1) node[draw](i){$i$}
(4,-1) node[draw](j){$j$};
\draw[<-]  (a)--(b); \draw  (a)--(c); 
\draw  (c)--(d); \draw[->]  (b)--(f); 
\draw  (d)--(f); \draw  (d)--(e); 
\draw  (e)--(g); \draw  (d)--(h); 
\draw  (h)--(i); \draw  (i)--(j); \draw  (i)--(g); 
\end{tikzpicture}

File=[a,f]
\end{frame}
  
  
  

\begin{frame}
 \frametitle{Exercice à rendre 1 -- Un corrigé}
   
 \begin{tikzpicture}
\path
(0,0) node[draw,fill,black](a){\color{white}{$a$}}
(0,1) node[draw,fill,black](b){\color{white}{$b$}}
(1,0) node[draw,fill,gray!20](c){\color{white}{$c$}}
(2,0) node[draw](d){$d$}
(3,0) node[draw](e){$e$}
(2,1) node[draw,fill,gray!20](f){\color{white}{$f$}}
(4,0) node[draw](g){$g$}
(2,-1) node[draw](h){$h$}
(3,-1) node[draw](i){$i$}
(4,-1) node[draw](j){$j$};
\draw[<-]  (a)--(b); \draw[->] (a)--(c); 
\draw  (c)--(d); \draw[->]  (b)--(f); 
\draw  (d)--(f); \draw  (d)--(e); 
\draw  (e)--(g); \draw  (d)--(h); 
\draw  (h)--(i); \draw  (i)--(j); \draw  (i)--(g); 
\end{tikzpicture}

File=[f, c]
\end{frame}
  
  

\begin{frame}
 \frametitle{Exercice à rendre 1 -- Un corrigé}
   
 \begin{tikzpicture}
\path
(0,0) node[draw,fill,black](a){\color{white}{$a$}}
(0,1) node[draw,fill,black](b){\color{white}{$b$}}
(1,0) node[draw,fill,gray!20](c){\color{white}{$c$}}
(2,0) node[draw,fill,gray!20](d){\color{white}{$d$}}
(3,0) node[draw](e){$e$}
(2,1) node[draw,fill,black](f){\color{white}{$f$}}
(4,0) node[draw](g){$g$}
(2,-1) node[draw](h){$h$}
(3,-1) node[draw](i){$i$}
(4,-1) node[draw](j){$j$};
\draw[<-]  (a)--(b); \draw[->] (a)--(c); 
\draw  (c)--(d); \draw[->]  (b)--(f); 
\draw[<-]  (d)--(f); \draw  (d)--(e); 
\draw  (e)--(g); \draw  (d)--(h); 
\draw  (h)--(i); \draw  (i)--(j); \draw  (i)--(g); 
\end{tikzpicture}

File=[ c, d]
\end{frame}












\begin{frame}
 \frametitle{Exercice à rendre 1 -- Un corrigé}
   
 \begin{tikzpicture}
\path
(0,0) node[draw,fill,black](a){\color{white}{$a$}}
(0,1) node[draw,fill,black](b){\color{white}{$b$}}
(1,0) node[draw,fill,black](c){\color{white}{$c$}}
(2,0) node[draw,fill,gray!20](d){\color{white}{$d$}}
(3,0) node[draw](e){$e$}
(2,1) node[draw,fill,black](f){\color{white}{$f$}}
(4,0) node[draw](g){$g$}
(2,-1) node[draw](h){$h$}
(3,-1) node[draw](i){$i$}
(4,-1) node[draw](j){$j$};
\draw[<-]  (a)--(b); \draw[->] (a)--(c); 
\draw  (c)--(d); \draw[->]  (b)--(f); 
\draw[<-]  (d)--(f); \draw  (d)--(e); 
\draw  (e)--(g); \draw  (d)--(h); 
\draw  (h)--(i); \draw  (i)--(j); \draw  (i)--(g); 
\end{tikzpicture}

File=[  d]
\end{frame}






\begin{frame}
 \frametitle{Exercice à rendre 1 -- Un corrigé}
   
 \begin{tikzpicture}
\path
(0,0) node[draw,fill,black](a){\color{white}{$a$}}
(0,1) node[draw,fill,black](b){\color{white}{$b$}}
(1,0) node[draw,fill,black](c){\color{white}{$c$}}
(2,0) node[draw,fill,black](d){\color{white}{$d$}}
(3,0) node[draw,fill,gray!20](e){\color{white}{$e$}}
(2,1) node[draw,fill,black](f){\color{white}{$f$}}
(4,0) node[draw](g){$g$}
(2,-1) node[draw,fill,gray!20](h){\color{white}{$h$}}
(3,-1) node[draw](i){$i$}
(4,-1) node[draw](j){$j$};
\draw[<-]  (a)--(b); \draw[->] (a)--(c); 
\draw  (c)--(d); \draw[->]  (b)--(f); 
\draw[<-]  (d)--(f); \draw[->]  (d)--(e); 
\draw  (e)--(g); \draw[->]  (d)--(h); 
\draw  (h)--(i); \draw  (i)--(j); \draw  (i)--(g); 
\end{tikzpicture}

File=[ e, h]
\end{frame}
  
  
  
  
  
\begin{frame}
 \frametitle{Exercice à rendre 1 -- Un corrigé}
   
 \begin{tikzpicture}
\path
(0,0) node[draw,fill,black](a){\color{white}{$a$}}
(0,1) node[draw,fill,black](b){\color{white}{$b$}}
(1,0) node[draw,fill,black](c){\color{white}{$c$}}
(2,0) node[draw,fill,black](d){\color{white}{$d$}}
(3,0) node[draw,fill,black](e){\color{white}{$e$}}
(2,1) node[draw,fill,black](f){\color{white}{$f$}}
(4,0) node[draw,fill,gray!20](g){\color{white}{$g$}}
(2,-1) node[draw,fill,gray!20](h){\color{white}{$h$}}
(3,-1) node[draw](i){$i$}
(4,-1) node[draw](j){$j$};
\draw[<-]  (a)--(b); \draw[->] (a)--(c); 
\draw  (c)--(d); \draw[->]  (b)--(f); 
\draw[<-]  (d)--(f); \draw[->]  (d)--(e); 
\draw[->]  (e)--(g); \draw[->]  (d)--(h); 
\draw  (h)--(i); \draw  (i)--(j); \draw  (i)--(g); 
\end{tikzpicture}

File=[   h , g]
\end{frame}
  
  
 
\begin{frame}
 \frametitle{Exercice à rendre 1 -- Un corrigé}
   
 \begin{tikzpicture}
\path
(0,0) node[draw,fill,black](a){\color{white}{$a$}}
(0,1) node[draw,fill,black](b){\color{white}{$b$}}
(1,0) node[draw,fill,black](c){\color{white}{$c$}}
(2,0) node[draw,fill,black](d){\color{white}{$d$}}
(3,0) node[draw,fill,black](e){\color{white}{$e$}}
(2,1) node[draw,fill,black](f){\color{white}{$f$}}
(4,0) node[draw,fill,gray!20](g){\color{white}{$g$}}
(2,-1) node[draw,fill,black](h){\color{white}{$h$}}
(3,-1) node[draw,fill,gray!20](i){\color{white}{$i$}}
(4,-1) node[draw](j){$j$};
\draw[<-]  (a)--(b); \draw[->] (a)--(c); 
\draw  (c)--(d); \draw[->]  (b)--(f); 
\draw[<-]  (d)--(f); \draw[->]  (d)--(e); 
\draw[->]  (e)--(g); \draw[->]  (d)--(h); 
\draw[->]  (h)--(i); \draw  (i)--(j); \draw  (i)--(g); 
\end{tikzpicture}

File=[    g , i ]
\end{frame}
  
  
  
 
\begin{frame}
 \frametitle{Exercice à rendre 1 -- Un corrigé}
   
 \begin{tikzpicture}
\path
(0,0) node[draw,fill,black](a){\color{white}{$a$}}
(0,1) node[draw,fill,black](b){\color{white}{$b$}}
(1,0) node[draw,fill,black](c){\color{white}{$c$}}
(2,0) node[draw,fill,black](d){\color{white}{$d$}}
(3,0) node[draw,fill,black](e){\color{white}{$e$}}
(2,1) node[draw,fill,black](f){\color{white}{$f$}}
(4,0) node[draw,fill,black](g){\color{white}{$g$}}
(2,-1) node[draw,fill,black](h){\color{white}{$h$}}
(3,-1) node[draw,fill,gray!20](i){\color{white}{$i$}}
(4,-1) node[draw](j){$j$};
\draw[<-]  (a)--(b); \draw[->] (a)--(c); 
\draw  (c)--(d); \draw[->]  (b)--(f); 
\draw[<-]  (d)--(f); \draw[->]  (d)--(e); 
\draw[->]  (e)--(g); \draw[->]  (d)--(h); 
\draw[->]  (h)--(i); \draw  (i)--(j); \draw  (i)--(g); 
\end{tikzpicture}

File=[    i ]
\end{frame}
  
  
  
  
\begin{frame}
 \frametitle{Exercice à rendre 1 -- Un corrigé}
   
 \begin{tikzpicture}
\path
(0,0) node[draw,fill,black](a){\color{white}{$a$}}
(0,1) node[draw,fill,black](b){\color{white}{$b$}}
(1,0) node[draw,fill,black](c){\color{white}{$c$}}
(2,0) node[draw,fill,black](d){\color{white}{$d$}}
(3,0) node[draw,fill,black](e){\color{white}{$e$}}
(2,1) node[draw,fill,black](f){\color{white}{$f$}}
(4,0) node[draw,fill,black](g){\color{white}{$g$}}
(2,-1) node[draw,fill,black](h){\color{white}{$h$}}
(3,-1) node[draw,fill,black](i){\color{white}{$i$}}
(4,-1) node[draw,fill,gray!20](j){\color{white}{$j$}};
\draw[<-]  (a)--(b); \draw[->] (a)--(c); 
\draw  (c)--(d); \draw[->]  (b)--(f); 
\draw[<-]  (d)--(f); \draw[->]  (d)--(e); 
\draw[->]  (e)--(g); \draw[->]  (d)--(h); 
\draw[->]  (h)--(i); \draw[->]  (i)--(j); \draw  (i)--(g); 
\end{tikzpicture}

File=[   j]
\end{frame}



  
\begin{frame}
 \frametitle{Exercice à rendre 1 -- Un corrigé}
   
 \begin{tikzpicture}[>=triangle 45,x=1.5cm,y=1.8cm]
\path
(0,0) node[draw,fill,black](a){\color{white}{$a$}}
(0,1) node[draw,fill,black](b){\color{white}{$b$}}
(1,0) node[draw,fill,black](c){\color{white}{$c$}}
(2,0) node[draw,fill,black](d){\color{white}{$d$}}
(3,0) node[draw,fill,black](e){\color{white}{$e$}}
(2,1) node[draw,fill,black](f){\color{white}{$f$}}
(4,0) node[draw,fill,black](g){\color{white}{$g$}}
(2,-1) node[draw,fill,black](h){\color{white}{$h$}}
(3,-1) node[draw,fill,black](i){\color{white}{$i$}}
(4,-1) node[draw,fill,black](j){\color{white}{$j$}};
\draw[<-]  (a)--(b); \draw[->] (a)--(c); 
\draw[dashed]  (c)--(d); \draw[->]  (b)--(f); 
\draw[<-]  (d)--(f); \draw[->]  (d)--(e); 
\draw[->]  (e)--(g); \draw[->]  (d)--(h); 
\draw[->]  (h)--(i); \draw[->]  (i)--(j); \draw[dashed]  (i)--(g); 
\end{tikzpicture}

File=[     ]
\end{frame}


  \end{resolution}

    
  
  
  \begin{frame}
   \frametitle{Application}
   
   \textbf{Exercice à rendre 2.} 
   En utilisant le programme précédent, on définit la fonction suivante :
   \begin{codepython}
  def f(G,s,v):
  
\hp	P=bfs(G,s)
	
\hp		ch=[v]
	
\hp		while P[v]:
	
\hp	\hp			ch.append(P[v])
		
\hp	\hp			v=P[v]
		
\hp		ch.reverse()
	
\hp		return ch
	
print f(G,'b','h')

   \end{codepython}
   
   Quel est son rôle ? 
   
   
 
     \href{run:python/bfscodebref.py}{\beamerbutton{illustration}}
 
 
  \end{frame}
  
  
  
  
  %%%%%%%%%%%%%%%%%%%%%%%%%%%% 
  %%%%%%%%% CORRIGE EXERCICE 
  %%%%%%%%%%%%%%%%%%%%%%%%%
  
  
  \begin{resolution}

  
  
  \begin{frame}
   \frametitle{Rôle du programme}
   
   Ce programme renvoie le chemin de s à v défini  dans l'arborescence associée au parcours. 
   
   Avec f(G,b,h) :
   
   \scalebox{0.7}{
    \begin{tikzpicture}[>=triangle 45,x=1.5cm,y=1.8cm]
\path
(-1,-1) node[draw,fill,black,circle](a){\color{white}{$a$}}
(0,0) node[draw,fill,red,circle](b){\color{white}{$b$}}
(-2,-2) node[draw,fill,black,circle](c){\color{white}{$c$}}
(0,-1) node[draw,fill,black,circle](d){\color{white}{$d$}}
(1,-1) node[draw,fill,red,circle](e){\color{white}{$e$}}
(0,-2) node[draw,fill,black,circle](f){\color{white}{$f$}}
(2,-2) node[draw,fill,red,circle](g){\color{white}{$g$}}
(2,-3) node[draw,fill,red,circle](h){\color{white}{$h$}};
\draw[->]  (b)--(a); \draw[->]  (a)--(c); 
\draw[->]   (b)--(d); \draw[->,color=red]   (b)--(e); 
\draw[dashed]  (d)--(c); \draw[dashed]  (d)--(e); 
\draw[->]  (e)--(f); \draw[dashed]  (f)--(g); 
\draw[->,color=red]  (g)--(h); \draw[->,color=red]  (e)--(g); 
\end{tikzpicture}
}

C'est un plus court chemin de s à v dans le graphe de départ.
  \end{frame}

\end{resolution}
  %%%%%%%%%%%%%%%%%%%%%%%%%%%% 
  %%%%%%%%% FIN  CORRIGE EXERCICE 
  %%%%%%%%%%%%%%%%%%%%%%%%%
  
  
  
  
  


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

