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



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


 
 
\usepackage{verbatim}
 

\begin{document}

 \frame{\titlepage}


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

