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



% voir http://blog.dorian-depriester.fr/latex/tikz/tikz-externalisez-vos-figures-pour-gagner-en-temps-de-compilation/
% pour les 2 paquets suivants
\usetikzlibrary{external}
\tikzexternalize
 
\usepackage{verbatim}
%\let\resolution=\comment
%\let\endresolution=\endcomment

 \newenvironment{resolution}{ }{ }


\begin{document}

 \frame{\titlepage}


   
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
%%%%%%%%%%%%%%  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 
  %%%%%%%%%%%%%%%%%%%%%%%%%
  
  
  
  
   
  
 
\end{document}

