(* parcurgere prin cuprindere, graf orientat *)

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 mulțimea vecinilor *)
let add_edge_set gr (u, v) =        (* adaugă muchie la graf *)
  let vecini = try M.find u gr with Not_found -> S.empty
  in M.add u (S.add v vecini) gr

let gr_set = List.fold_left add_edge_set M.empty edges (* graful exemplu *)

(* mapunion f { n1, n2, ... nk } -> f(n1) U f(n2) U ... U f(nk) *)
(* vom calcula mulțimea vecinilor unei mulțimi de noduri *)
let mapunion f set = S.fold (fun e acc -> S.union (f e) acc) set S.empty

(* tipărește toate șirurile dintr-o mulțime, precedate de un mesaj *)
let print_set msg set = print_string msg; S.iter print_string set; print_newline()
                        
let bfs gr start =        (* parcurge de la start, returnează nodurile vizitate *)
  (* all = toate nodurile vizitate; crt = nodurile atinse în pasul curent *)
  let rec pas all crt =
    let vecini n = try M.find n gr with Not_found -> S.empty in
    let noduri_urm = mapunion vecini crt in        (* vecinii nodurilor din crt *)
    let crt' = S.diff noduri_urm all in                (* doar cei nevizitați *)
    (
      print_set "noduri curente: " crt;
      print_set "vecinii lor: " noduri_urm;
      print_set "vecinii noi: " crt';
      (* adaugă nodurile noi la vizitate, continuă din nodurile noi *)
      if S.is_empty crt' then all else pas (S.union all crt') crt'
    )
  in let sset = S.singleton start        (* lucrăm cu mulțimi *)
     in pas sset sset

let test  = bfs gr_set "a"

This document was generated using caml2html