Juste l’algorithme de Prim, commenté, en Caml Light

• Sujet

• Retour à la page des TP

let rec insère compare l e = match l with
	| [] -> [e]
	| h::t when compare e h -> e::h::t
	| h::t -> h::insère compare t e
;;

let extrait_min = function
	| [] -> invalid_arg "extract_min"
	| h::t -> h, t
;;

let graphe = [|[1,1;2,2];[2,3;3,4];[3,1];[]|];;

let prim graphe =
	let n = vect_length graphe in
	let visité = make_vect n false in
	visité.(0) <- true;
	let rec ajouter tas voisins j = match voisins with (* ajoute au tas les arêtes partant de j *)
		| [] -> tas
		| (k,p)::t -> ajouter (insère (fun (a,_,_) (b,_,_) -> a < b) tas (p,j,k)) t j (* sous la forme (poids, départ (j), arrivée) *)
	in let rec aux arbre tas =
		if tas = [] then arbre else (* plus de tas, on a fini *)
		let (p,i,j), tas = extract_min tas in
		if not visité.(j) then ( (* si cette arête ne joint pas deux sommets de l'arbre *)
			visité.(j) <- true;
			aux ((i,j)::arbre) (ajouter tas graphe.(j) j) (* on ajoute l'arête à l'arbre et on continue avec le tas augmenté des voisins de j *)
		) else (* sinon on jette l'arête *)
			aux arbre tas
	in aux [] (ajouter [] graphe.(0) 0) (* le tas est initialisé aux voisins de 0, mais ça marche aussi avec 1 et peut-être même avec 2 *)
;;

prim graphe;;