open Printf

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

(************* definirea grafurilor ************)

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") ]

(********* căutare în adâncime, dicționar: nod -> listă de vecini ******)
let add_edge_lst gr (u, v) =
  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

let dfs gr =
  let rec dfs1 vazute n =
    let vecini = try M.find n gr with Not_found -> []
    in if S.mem n vazute then vazute
       else (
         print_endline n;        (* afișează nod vizitat *)
         List.fold_left dfs1 (S.add n vazute) vecini
       )
  in dfs1 S.empty        (* inițial, nu avem noduri vizitate *)

let all1 = print_endline "DFS:"; dfs gr_lst "a"

(************ căutare prin cuprindere, dicționar: nod -> mulțime de vecini *)

let add_edge_set graf (u, v) =
  let vecini = try M.find u graf with Not_found -> S.empty
  in let gplus = M.add u (S.add v vecini) graf
     in if M.mem v graf then gplus else M.add v S.empty gplus

let gr_set = List.fold_left add_edge_set M.empty edges

let bfs gr start =
  let vecini n = M.find n gr in
  let rec pas vazute curente =
    S.iter (printf "%s ") curente; print_newline();

    (* pentru fiecare nod nou, adaugă vecinii la mulțimea celor văzute *)
    let vazut_plus = S.fold (fun n -> vecini n |> S.union) curente vazute
    in let noi = S.diff vazut_plus vazute        (* am găsit noduri noi ? *)
       in if S.is_empty noi then vazute else pas vazut_plus noi        (* continuă? *)
  in pas start start
        
let all2 = print_endline "BFS:"; bfs gr_set (S.singleton "a")

This document was generated using caml2html