Algorithmes de Prim et Kruskal

Cette séance de cours couvre l'exactitude et la mise en œuvre des algorithmes de Prim et Kruskal pour trouver un minimum d'arbres couvrants dans un graphique. L'algorithme de Prim commence avec un seul sommet et fait pousser l'arbre en ajoutant le bord de croisement de poids minimum. L'algorithme de Kruskal commence par une forêt vide et ajoute des arêtes qui ne créent pas de cycles. La séance de cours explique la propriété de coupe, les défis de la mise en œuvre et l'analyse des deux algorithmes, y compris l'utilisation de la structure de données des ensembles disjoints. Il traite également de la complexité temporelle des algorithmes et fournit des exemples de leur application.