Discussion :

[contremaitre]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[ToTo13]

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.

[contremaitre]

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

[Jean-Marc.Bourguet]

* 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).

* 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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[contremaitre]

Je vous remercie

[Jean-Marc.Bourguet]

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.