(* traversare în adâncime *)

module S = Set.Make(String)
module M = Map.Make(String)

let edges = [ ("a", "b"); ("b", "e"); ("e", "a");
  ("b", "f"); ("e", "f"); ("b", "c"); ("c", "d"); ("d", "c");
  ("d", "h"); ("h", "d"); ("h", "g"); ("f", "g"); ("g", "f") ]

(* graf: dicționar de la noduri la lista vecinilor *)
          
let add_edge_lst gr (u, v) =        (* adaugă o muchie la graf *)
  let vecini = try M.find u gr with Not_found -> []
  in M.add u (v::vecini) gr

let gr_lst = List.fold_left add_edge_lst M.empty edges        (* graful exemplu *)

let dfs gr =        (* parcurge în adâncime, returnează mulțimea nodurilor *)
  let rec visit vis n =  (* vizitez nodul n, am văzut multime vis *)
    if S.mem n vis then vis        (* nu avem noduri noi *)
    else (
      print_endline n;                (* pentru vizualizare *)
      let vecini = try M.find n gr with Not_found -> [] in
      (* adăugăm nodul la cele vizitate, continuăm din fiecare vecin *)
      List.fold_left visit (S.add n vis) vecini
    )
  in visit S.empty                (* inițial, nu avem noduri vizitate *)
   
let test = dfs gr_lst "a"        (* pornește de la nodul "a" *)

This document was generated using caml2html