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