8. Classes disjointes

Ce chapitre présente une structure de données impérative pour le problème des classes disjointes, connue sous le nom de union-find. Ce problème consiste à maintenir dans une structure de données une partition d'un ensemble fini, c'est-à-dire un découpage en sous-ensembles disjoints que l'on appelle des « classes ». On souhaite pouvoir déterminer si deux éléments appartiennent à la même classe et réunir deux classes en une seule. Ce sont ces deux opérations qui ont donné le nom de structure union-find.
programme page télécharger
71. Signature de la structure union-find 297 p71.ml
72. Structure union-find 298 p72.ml

Solution des exercices

On donne ici les solutions de certains exercices.
exercice page télécharger
solution 8.2 301 ex8_2.ml
solution 8.5 301 ex8_5.ml
solution 8.7 303 ex8_7.ml
solution 8.8 303 ex8_8.ml
Bien entendu, il existe le plus souvent beaucoup d'autres solutions.
Dernière mise à jour : 17/3/2016