Algorithmes de recherche d'arbres de recouvrement minimaux
Objectifs
Les deux algorithmes de recherche d'arbres de recouvrement minimaux les plus connus sont ceux de Kruskal et de Prim.
Ils sont tous les deux polynomiaux et leur construction repose, pour chacun d'entre eux, sur un petit théorème fondamental qui permet de prouver qu'ils donnent bien une des solutions optimales (il y a rarement unicité de la solution optimale).
Le module a pour objectif à la fois de montrer comment, grâce à un théorème, on obtient facilement des algorithmes spécifiques à ces problèmes et également d'illustrer le fonctionnement de ces algorithmes et l'optimisation de leur programmation si on utilise les structures de données adéquates.
