Parcours de graphes


1  Graphes (rappels)

Un graphe est un couple (X,E) où X est un ensemble fini quelconque dit ensembles de sommets et E un ensmble de couples d'éléments de X ou une ensemble de paires1 d'élément de X suivant que le graphe est orienté ou non.


Pour tout xÎ X, on définit l'ensemble, noté Adj(x,G), des sommets adjacents à x dans G
orienté
Adj(x,G)={yÎ X | (x,y)Î E}
non orienté
Adj(x,G)={yÎ X | {x,y}Î E }

2  Parcours en profondeur d'abord

On considère, dans un premier temps un parcours en profondeur à partir d'un certain sommet sÎ X.


On suppose disposer sur les éléments de X d'une fonction booléenne Vu. On peut modifier, en un point x la valeur de cette fonction par Voir(x), et alors Vu(x) est vrai, ou par Cacher(x), et alors Vu(x) est faux.


Soient P une pile et L une liste.
  Procédure PP(s,G) :
  1. Pour tout uÎ X faire Cacher(u) Fpour;
  2. P¬ (s);
  3. Voir(s);
  4. L¬Ø;
  5. Tant que P¹Ø faire
  6.   u¬ Tete(P);
  7.   Si il existe vÎ Adj(u) tel que ¬ Vu(v) alors
  8.     Empiler(v,P); Voir(v);
  9.   Sinon
  10.     Depiler(P); Ajouter(u,L);
  11.   Fsi
  12. Ftantque
  13. Retourner(L)
  Fproc


Nous proposons ci-dessous une implémentation en camllight de cet algorithme :

La fonction Vu
let vus = ref ([]:int list);;

let init_vu() = vus:=[];;

let voir s = vus := s::!vus;;

let vu s = List.mem s !vus;;
Les piles
type 'a stack = ('a list) ref;;

let new_stack () = ((ref []):'a stack);;

let push a (s:'a stack) = s:=a::!s;;

exception Empty_stack;;

let top (s:'a stack) = 
 try List.hd !s with _ -> raise Empty_stack;;

let pop (s:'a stack) = 
 try s := List.tl !s with _ -> raise Empty_stack;;
 
let is_empty (s:'a stack) = (!s=[]) ;;
Le programme
(* -- find : selectionne le 'x' element d'une liste qui
             satisfait le critere 'c'                   *)
let rec find c = function
 [] -> raise Not_found
|x::xs -> if (c x) then x else find c xs
;;

(* -- adjs : fournit la liste des sommets adjacents a
             sont premier argumant                      *)
(* NB : son implementation depend de la representation
   du graphe; nous ne la precisons pas ici              *)

(* -- Le programme *)
let pp s g =
 let l = ref ([]:int list) in
 let sp = new_stack() in
   init_vu();
   push s sp;
   voir s;
   while not(is_empty sp) do
    let u = top sp in
     (try 
      let v = find (fun v -> not (vu v)) (adjs u g) in
       begin push v sp; voir v end
     with Not_found -> pop sp; l := u::!l)
   done;
   !l
;;

L'algorithme PP ne donne un parcours du graphe G que si G est (fortement) connexe. Pour obtenir un parcours dans le cas général, il faut itérer PP sur l'ensemble des sommets. On parcours ainsi toutes les composantes connexes. On ne peut plus alors réeelemnt parler d'un parcours à partir d'un sommet donné.

  Procédure GPP(G) :
  1. Pour tout uÎ X faire Cacher(u) Fpour;
  2. P¬Ø;
  3. L¬Ø;
  4. Pour tout sÎ X faire
  5.   Voir(s);
  6.   Empiler(s,P);
  7.   Tant que P¹Ø faire
  8.     u¬ Tete(P);
  9.     Si il existe vÎ Adj(u) tel que ¬ Vu(v) alors
  10.       Empiler(v,P); Voir(v);
  11.     Sinon
  12.       Depiler(P); Ajouter(u,L);
  13.     Fsi
  14.   Ftantque;
  15. Fpour;
  16. Retourner(L);
  Fproc


On peut, trés facilement donner une version récursive d'un algorithme de parcours en profondeur. La pile explicitement gérée dans PP devient la pile (implicite) des appels récursifs.

  Procédure RPP(s,G,L) :
  1. Voir(s);
  2. Pour tout uÎ Adj(s) faire
  3.   Si ¬ Vu(u) alors RPP(u,G,L) Fsi;
  4. Fpour;
  5. Ajouter(s,L);
  Fproc


On obtient alors l'algorithme général
  Procédure GRPP(s,G,L) :
  1. L¬Ø;
  2. Pour tout sÎ X faire Cacher(s) Fpour;
  3. Pour tout sÎ X faire GRPP(s,G,L) Fpour;
  4. Retourner(L);
  Fproc


3  Parcours en largeur

Soit F une file.
  Procédure PL(s,G) :
  1. Pour tout uÎ X faire Cacher(u) Fpour;
  2. F¬ (s);
  3. Voir(s);
  4. L¬(s);
  5. Tant que F¹Ø faire
  6.   u¬ Tete(F);
  7.   Pour tout vÎ Adj(u) tel que ¬ Vu(v) faire
  8.     Enfiler(v,F); Voir(v); Ajouter(v,L);
  9.   Fpour;
  10.   Defiler(F);
  11. Ftantque
  12. Retourner(L)
  Fproc

Les files
type 'a fifo = ('a list) ref;;

let new_fifo () = ((ref []):'a fifo);;

let is_empty (f:'a fifo) = (!f=[]);;

let in_fifo a f = f:=a::!f;;

exception Empty_fifo;;

let hd_fifo (f:'a fifo) = 
 try List.hd (List.rev !f) with _ -> raise Empty_fifo
;;

let out_fifo (f:'a fifo) =
 try f := List.rev(List.tl(List.rev !f)) with _ -> raise Empty_fifo
;;
Le programme
let pl s g =
 let l = ref ([]:int list) in
 let f = new_fifo() in
  init_vu();
  in_fifo s f;
  voir s;
  l := s::!l;
  while not(is_empty f) do
   let u = hd_fifo f in
   List.iter
    (fun v 
     -> if not(vu v) then (voir v; l := v::!l; in_fifo v f))
    (adjs u g);
   out_fifo f
  done;
  !l
;;
1
dans un couple l'ordre des éléments importe mais pas dans une paire. De plus, une paire peut ne contenir qu'un seul élément. Les couples sont notés (x,y) et si x¹ y alors (x,y)¹(y,x) Les paires sont notées {x,y} et {x,x}={x} et {x,y}={y,x}
This document was translated from LATEX by HEVEA.

Page précédente