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") ] let add_edge_list graf (u, v) = let vecini = try M.find u graf with Not_found -> [] in M.add u (v :: vecini) graf 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 grlist = List.fold_left add_edge_list M.empty edges let grset = List.fold_left add_edge_set M.empty edges (*************** afișare ************) let dotfile = "grtrav.dot" let showstep gr noi viz edgeiter = let nodes = M.fold (fun k _ -> S.add k) gr S.empty in let f = open_out dotfile in let printedge n dest = fprintf f "%s -> { " n; edgeiter (fprintf f "%s ") dest; output_string f "}\n" in output_string f "digraph {\n"; S.iter (fun n -> output_string f n; output_string f (if S.mem n noi then " [color=red] " else if S.mem n viz then " [style=filled] " else " ")) nodes; M.iter printedge gr; output_string f "}\n"; close_out f; Sys.command ("dotty " ^ dotfile) |> ignore; read_line() |> ignore (*********** parcurgere în adâncime **************) let dfs gr = let rec dfs1 vazute nod = if S.mem nod vazute then vazute else ( showstep gr (S.singleton nod) vazute List.iter; let vecini = M.find nod gr in List.fold_left dfs1 (S.add nod vazute) vecini ) in dfs1 S.empty (************ parcurgere prin cuprindere **************) let bfs gr start = let vecini n = M.find n gr in let rec pas vazute curente = showstep gr curente vazute S.iter; (* scrie; afișează; așteaptă enter *) (* 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 all1 = dfs grlist "a" (* |> S.elements *) *) let all2 = bfs grset (S.singleton "a") (* |> S.elements *)
This document was generated using caml2html