module M = Map.Make(String) module S = Set.Make(String) (* graf: dictionar nod -> lista de noduri *) 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") ] let add_edge dict (u, v) = let vecini = try M.find u dict with Not_found -> [] in M.add u (v :: vecini) dict let graf = List.fold_left add_edge M.empty edges let dfs gr = let rec dfs1 vazute nod = if S.mem nod vazute then vazute else ( print_endline nod; let vecini = M.find nod gr in List.fold_left dfs1 (S.add nod vazute) vecini ) in dfs1 S.empty (* ;; S.elements (dfs graf "a") ;; *) let addlist lst mult = List.fold_left (fun m e -> S.add e m) mult lst let bfs gr start = let rec pasi vechi noi = S.iter print_string noi; print_newline(); (* pentru urmărire *) let vechi = S.union vechi noi in (* adaugă nodurile curente *) let urm = S.fold (fun e -> addlist (M.find e gr)) noi S.empty in let noi = S.diff urm vechi in (* elimină cele deja văzute *) if S.is_empty noi then vechi else pasi vechi noi in pasi S.empty (S.singleton start) let all = S.elements (bfs graf "a")
This document was generated using caml2html