Arbres d'éclaboussure minimum: Algorithme de Prim

Cette séance de cours couvre le concept de spanning minimum, en commençant par un récapitulatif des structures de données disjointes. Il explique les opérations impliquées dans le maintien des ensembles disjoints et la représentation de la liste des ensembles. La séance de cours explore ensuite différentes méthodes syndicales, y compris l'heuristique des syndicats pondérés et l'union par rang. Il traite de la forêt de la représentation des arbres et de la compression du chemin. Le pseudocode pour les opérations MAKE-SET, FIND-SET et UNION est présenté. L'analyse du temps de fonctionnement de ces opérations est également discutée. La séance de cours se termine par une explication de l'algorithme de Prim pour trouver les arbres couvrants minimum et la propriété coupée qui justifie son exactitude.