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



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


 

 
  
 
\end{document}

