Parcours en profondeur

Graphe utilisé pour les exemples :

let g_mat = [|
    [|0; 0; 0; 0; 0; 0; 1|];
    [|0; 0; 1; 1; 1; 0; 0|];
    [|0; 1; 0; 0; 1; 1; 0|];
    [|0; 1; 0; 0; 1; 0; 0|];
    [|0; 0; 1; 1; 0; 0; 0|];
    [|0; 0; 1; 0; 1; 0; 0|];
    [|1; 0; 0; 0; 0; 0; 0|];
|]

let g_list = [|[6]; [2; 3; 4]; [1; 4; 5]; [1; 4]; [1; 2; 3; 5]; [4; 2]; [0]|]

val g_mat : int array array =
  [|[|0; 0; 0; 0; 0; 0; 1|]; [|0; 0; 1; 1; 1; 0; 0|];
    [|0; 1; 0; 0; 1; 1; 0|]; [|0; 1; 0; 0; 1; 0; 0|];
    [|0; 0; 1; 1; 0; 0; 0|]; [|0; 0; 1; 0; 1; 0; 0|];
    [|1; 0; 0; 0; 0; 0; 0|]|]

val g_list : int list array =
  [|[6]; [2; 3; 4]; [1; 4; 5]; [1; 4]; [1; 2; 3; 5]; [4; 2]; [0]|]

Parcours en profondeur sur liste d’adjacence

let dfs g r =
    let n = Array.length g in
    let seen = Array.make n false in
    let rec aux v =
        if not seen.(v) then (
            seen.(v) <- true;
            Printf.printf "Sommet %d visité\n%!" v;
            List.iter aux g.(v)
        ) in
    aux r

val dfs : int list array -> int -> unit = <fun>

let () = dfs g_list 0

Sommet 0 visité
Sommet 6 visité

let () = dfs g_list 3

Sommet 3 visité
Sommet 1 visité
Sommet 2 visité
Sommet 4 visité
Sommet 5 visité

Parcours en profondeur sur matrice d’adjacence

let dfs g r =
    let n = Array.length g in
    let seen = Array.make n false in
    let rec aux v =
        if not seen.(v) then (
            seen.(v) <- true;
            Printf.printf "Sommet %d visité\n%!" v;
            for j = 0 to n - 1 do
                if g.(v).(j) = 1 then aux j
            done
        ) in
    aux r

val dfs : int array array -> int -> unit = <fun>

let () = dfs g_mat 0

Sommet 0 visité
Sommet 6 visité

let () = dfs g_mat 3

Sommet 3 visité
Sommet 1 visité
Sommet 2 visité
Sommet 4 visité
Sommet 5 visité

Recherche de cycle

Graphe non-orienté

let has_cycle g = (* g : graphe non orienté représenté par liste d'adjacence *)
	let n = Array.length g in
    let pred = Array.make n (-1) in
    let ans = ref false in
    let rec aux p u = (* p a permis de découvrir u *)
        if pred.(u) = -1 then (
            pred.(u) <- p;
            List.iter (aux p) g.(u)
        )
        else if pred.(p) <> u then ans := true in
    for i = 0 to n - 1 do
        aux i i (* cherche un cycle depuis le sommet i *)
    done;
    !ans;;

has_cycle g_list

val has_cycle : int list array -> bool = <fun>

- : bool = true

Graphe orienté

let has_cycle g = (* g : graphe orienté représenté par liste d'adjacence *)
    let n = Array.length g in
	let visited = Array.make n 0 in
    let ans = ref false in
    let rec aux v = match visited.(v) with
        | 0 -> visited.(v) <- 1;
               List.iter aux g.(v);
               visited.(v) <- 2
        | 1 -> ans := true
        | _ -> () in
    for i = 0 to n - 1 do
        aux i (* cherche un cycle depuis le sommet i *)
    done;
    !ans

val has_cycle : int list array -> bool = <fun>