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.