structure de donnée Union-Find

Bonjour,

Je n'arrive pas à bien comprendre la structure de données apellée : "Disjoint-set data structure"

Meme si elle est bien expliqué sur wikipedia - disjoint-set data structure ou un exemple d'implementation ici : LiteratePrograms Disjoint set



Ce que je ne comprends pas c'est l'opération de find, elle est partout décrite par

Code:

---

1 2 3 4 5 6

function Find(x) if x.parent == x return x else return Find(x.parent)

---

Et c'est censé retourner la racine.
Mais le problème c'est :
* Comment on fait pour savoir si un élément se trouve dans la structure ou pas.
* On ne possède pas un pointeur vers tous les éléments, donc comment connaitre x.parent si on n'a pas de pointeur vers x...

Exemple, j'ai 3 liste A, B, C avec dedans des elements numérotés de 1 à n.
Si je faut A.find(1), je vois pas comment ca peut marcher.

Merci

Bonjour,

d'après ce que je vois, tu as une structure dans laquelle chaque noeud connait son père. La racine pointe vers elle même car elle n'a pas de père.
Ta fonction "Find" cherche la racine de l'ensemble que tu étudies :
- si x = x.parent alors on est à la racine et on retourne x.
- sinon on retrounera(x.parent), autrement dit on regardera un cran au dessus dans la hierarchie.

Pour ce qui est de ton problème d'ensembles disjoints, tu sauras si deux éléments sont dans le même ensemble si la racine est la même.

Merci pour cette réponse.

Donc cela veut dire qu'il faut connaitre le lien vers tous les éléments.
Et pour savoir si par exemple 2 et 4 sont dans le meme ensemble il faut deja que je cherche les élément 2 et 4 (dans une liste chainée par exemple), que je trouve leurs peres et que je les compares...
Mais trouver 2 et 4 se fait en O(n) dans une liste.
Donc je gagne du temps grace à cette structure pour connaitre la classe d'un élément mais ca m'aide pas pour rechercher un élément.
J'avais mal compris alors.

Merci

Citation:

---

Envoyé par pasdeface

* Comment on fait pour savoir si un élément se trouve dans la structure ou pas.

---

Un element est toujours dans un ensemble. C'est un systeme qui permet de faire des partitions (generalement au depart degeneree: chaque element est dans sa partition a lui tout seul, et apres on construit les partitions par fusion -- d'autres operations sont possibles mais plus complexes, la structure est optimisee pour celle-la). Les partitions sont identifiees par un element (la racine) qui est choisi plus ou moins au hasard (dans une fusion, c'est la racine d'un des deux ensembles fusionnes).

Citation:

---

* On ne possède pas un pointeur vers tous les éléments, donc comment connaitre x.parent si on n'a pas de pointeur vers x...

---

Tu te fais un tableau indexe par tes elements et tu es parti.

Note, generalement on associe au find de la compression pour accelerer les recherches suivantes (version avec tableau pour expliciter le point precedant):

Code:

---

1 2 3 4 5 6 7 8 9

PROCEDURE find(x) IS IF (parent[x] = x) THEN RETURN x ELSE VAR result = find(parent[x]) parent[x] = result RETURN result ENDIF END

---

Je vous remercie

Citation:

---

Envoyé par pasdeface

Merci pour cette réponse.

Donc cela veut dire qu'il faut connaitre le lien vers tous les éléments.
Et pour savoir si par exemple 2 et 4 sont dans le meme ensemble il faut deja que je cherche les élément 2 et 4 (dans une liste chainée par exemple), que je trouve leurs peres et que je les compares...
Mais trouver 2 et 4 se fait en O(n) dans une liste.
Donc je gagne du temps grace à cette structure pour connaitre la classe d'un élément mais ca m'aide pas pour rechercher un élément.
J'avais mal compris alors.

---

Tu peux maintenir des listes chainees (ou tout autre conteneur) en parallele de la structure d'Union-Join si tu as besoin a la fois d'iterer et de savoir si deux elements sont dans la meme partition.