Info_MPSI/MP/concours/Deuxieme annee/graphes.ml

type graphe = int list array;;
let rec parcours_dfs_aux (g:graphe) (listevue:int list) (listeavoir:int list):unit = match listeavoir with
| [] -> ()
| t::q -> if (List.mem t listevue) then parcours_dfs_aux g listevue q
  else
    begin
      parcours_dfs_aux g (t::listevue) (g.(t)@q)
    end;;

let parcours_profondeur (g:graphe) (sommet:int):unit = parcours_dfs_aux g [] [sommet];;

let rec bfs_aux (g:graphe) (listevue:int list) (listeavoir:int list):int list = match listeavoir with
| [] -> listevue
| t::q -> if (List.mem t listevue) then bfs_aux g listevue q
  else
    begin
      bfs_aux g (t::listevue) (q@g.(t))
    end;;

let connexe g = let parcours = bfs_aux g [] [0] in
  if (List.length parcours = List.length g) then true
  else false;;

let composantes_connexes g = let n = Array.length g in
  let cc = Array.make n 0 in
    for s = 0 to n-1 do
      if (cc.(s) = 0) then
        begin
          let parcours = bfs_aux g [] [s] in
          List.iter (fun x -> cc.(x) <- s+1) parcours
        end
      done;
    cc;;