Graphe biparti

let est_biparti adj =
  let n = Array.length adj in
  let couleur = Array.make n (-1) in       (* -1 non colorié, 0 ou 1 *)
  let ok = ref true in
  let f = Queue.create () in
  for depart = 0 to n - 1 do
    if couleur.(depart) = -1 then begin
      couleur.(depart) <- 0;
      Queue.push depart f;
      while not (Queue.is_empty f) do
        let s = Queue.pop f in
        List.iter (fun v ->
          if couleur.(v) = -1 then begin
            couleur.(v) <- 1 - couleur.(s); Queue.push v f
          end
          else if couleur.(v) = couleur.(s) then ok := false
        ) adj.(s)
      done
    end
  done;
  !ok

Un BFS colorie chaque sommet de la couleur opposée à son prédécesseur. Si l'on rencontre un voisin déjà colorié de la même couleur, le graphe n'est pas biparti (il contient un cycle impair). La boucle externe traite toutes les composantes.