Tutoriel par Examples: disjoints



La méthodologie forestière ci-dessus est en réalité une structure de données disjointe, qui implique trois opérations principales: subalgo makeSet(v: a node): v.parent = v <- make a new tree rooted at v subalgo findSet(v: a node): if v.parent == v: return v re...
Nous pouvons faire deux choses pour améliorer les sous-algorithmes simples et sous-optimaux des ensembles disjoints: Heuristique de compression de chemin : findSet ne doit jamais manipuler un arbre de hauteur supérieure à 2 . S'il finit par itérer un tel arbre, il peut lier directement les nœu...

Page 1 de 1