(* QUESTION 1 ============================================================== *)

let n = 7;;
let adj = [
  0,1, 7; 0,3, 5; 1,2, 8;
  1,3, 9; 1,4, 7; 2,4, 5;
  3,4,15; 3,5, 6; 4,5, 8;
  4,6, 9; 5,6,11
];;

(* QUESTION 2 ============================================================== *)

let proxim n = 
  (* Trois tableaux (b,n,d) : 
       b = est-ce que le noeud est encore dans le conteneur?
       d = quelle est la distance au noeud déjà traité le
           plus proche (max_int si aucun tel noeud n'existe) ?
       p = quel est le noeud déjà traité le plus proche?
  *)
  let b = make_vect n true
  and p = make_vect n 0
  and d = make_vect n max_int 
  in

  let trouver_max () = 
    let m = ref (-1) and md = ref max_int in
    for i = 0 to n-1 do
      if b.(i) && !md > d.(i) then (m := i; md := d.(i))
    done;
    if !md = max_int || not b.(!m) then 
      failwith "Plus aucun noeud n'existe!"
    else (!m, p.(!m))

  and retirer_noeud r adj =
    b.(r) <- false;
    d.(r) <- max_int;
    do_list 
      (fun (j,d') -> if b.(j) && d.(j) > d' then ( d.(j) <- d'; p.(j) <- r))
      adj

  in

  trouver_max, retirer_noeud
;;

(* QUESTION 3 ============================================================== *)

let prim n adj =
  let vadj = make_vect n [] in
  do_list (fun (i, j, w) -> 
    vadj.(i) <- (j,w) :: vadj.(i);
    vadj.(j) <- (i,w) :: vadj.(j)) adj;
  let (proche, retirer) = proxim n in
  let r = ref [] and d = ref 0 in
  for i = 0 to n-2 do
    retirer !d vadj.(!d);
    let (n,j) = proche () in
    r := (j,n) :: !r;
    d := n;
  done;
  !r
;;

prim n adj;;
    
      
(* QUESTION 4 ============================================================== *)

(* L'algorithme, tel qu'il est écrit, exécute O(n) fois les fonctions
   retirer et proche. Chacune de ces fonctions travaille en O(n). Sa 
   complexité totale est O(n²). 

   Pour des raisons évidentes (toutes les boucles ou récursions apparaissant 
   dans l'algorithme s'appliquent à un nombre fini de valeurs) l'algorithme
   termine toujours.

   On peut envisager des manières d'écrire retirer et proche qui permettent
   d'avoir une complexité moindre (par exemple, O(E log n) en utilisant un
   tas, où E est le nombre d'arêtes). 
*)

(* QUESTION 5 ============================================================== *)

(* Il faut montrer que l'algorithme génère un arbre couvrant. 

   Pour cela, il faut montrer:

   - que l'ensemble obtenu est connexe (il relie tous les sommets au sommet
     zéro). 

   On se sert de l'invariant de boucle disant que les noeuds ajoutés 
   forment un ensemble connexe. Puisque ajouter un noeud 'N' ajoute 
   également une arête le reliant à un noeud précédemment ajouté 'M', 
   et que 'M' est relié à tous les noeuds déjà ajoutés par invariant,
   alors 'N' est à travers 'M' relié à tous les noeuds déjà existants. 

   Donc, lorsque tous les noeuds ont été ajoutés, ils forment 
   bien un ensemble connexe.

   - que l'ensemble obtenu est acyclique (il n'existe pas deux chemins 
     distincts reliant deux noeuds). 
   
   Supposons que l'ensemble soit acyclique. Puisqu'il ne l'est pas 
   initialiement (l'ensemble à un élément est toujours acyclique), il l'est 
   devenu lors de l'ajout d'une arête (N,M). Cela signifie qu'il existait
   exactement un chemin de 'N' à 'M' avant l'ajout de cette arête, puisque
   l'ajout de l'arête en a créé un deuxième. Or, c'est impossible,
   puisqu'il n'existe de chemin de 'N' à 'M' que si 'N' et 'M' ont déjà 
   été ajoutés à l'ensemble, et que si 'N' et 'M' sont déjà dans 
   l'ensemble alors l'algorithme ne sélectionnera pas (N,M).

   Donc, l'algorithme conserve l'ensemble acyclique.

   Donc, l'ensemble généré par l'algorithme est un arbre couvrant.
*)

(* QUESTION 6 ============================================================== *)

(* Soit A un arbre couvrant minimal du graphe, et B l'arbre couvrant
   créé par l'algorithme. L'algorithme construit B arête par arête, 
   et on considère que seules les m(A) premières arêtes ajoutées à B sont 
   également dans A. Si m(A) = n, alors A = B et donc l'arbre est minimal.

   Sinon, on construit un arbre A' tel que m(A') = m(A) + 1, ce qui permet
   de conclure par récurrence sur n - m(A).

   Pour construire cet arbre, on note (M,N) la première arête de B
   qui n'est pas dans A, et on note C(M) l'ensemble des arêtes ajoutées
   à B avant celle-ci (ces arêtes sont donc également dans A). 

   Il existe un chemin de M à N dans A (puisque A est couvrant, donc 
   connexe), et ce chemin comporte au moins une arête (O,P) qui n'est pas 
   dans B (puisque B est couvrant, donc acyclique). On choisit P comme le
   premier point du chemin issu de M qui n'est pas dans C(M), et donc 
   O est implicitement dans C(M). Et donc, (O,P) est un candidat à 
   l'ajout au même titre que (M,N) : les deux ont un noeud (O/M) dans 
   l'ensemble connecté et un noeud (P/N) au-dehors. Donc, puisque 
   c'est (M,N) qui a été choisi:
   
     p(M,N) <= p(O,P)

   Alors, on construit l'ensemble A' = A + (M,N) - (O,P), dont le poids
   est inférieur ou égal à celui de A à cause de cette inégalité. Il faut
   maintenant montrer que cet ensemble est un arbre couvrant: pour cela, 
   on remarque qu'il existe dans A et A' les mêmes chemins de M à O et 
   de N à P (qui ne sont pas affectés par la suppression de (M,N) ou (O,P))
   et donc qu'un chemin allant de X à Y dans A et passant par (M,N) 
   peut être redirigé pour effectuer X -> M -> O -> P -> N -> Y à la
   place. Il n'y a pas de création de cycles suite à l'ajout de (O,P), 
   puisqu'elle relie deux ensembles déconnextés. 

   Donc A' est un arbre couvrant contenant (M,N), donc tel que 
   m(A') = m(A) + 1, et qui est également minimal. On conclut alors
   par récurrence.
*)