Δομή ξένων συνόλων (πληροφορική)

Στην πληροφορική, μια δομή ξένων συνόλων (Αγγλικά: disjoint-set data structure, γνωστή και ως union–find δομή ή σύνολο merge–find) είναι μια δομή δεδομένων η οποία χειρίζεται ένα σύνολο στοιχείων τα οποία διαχωρίζονται σε ένα αριθμό μη επικαλυπτόμενων υποσυνόλων (ή κλάσεων). Μια τέτοια δομή υποστηρίζει τις παρακάτω δύο βασικές λειτουργίες:

 Find (εύρεση): Καθορισμός σε ποιο υποσύνολο βρίσκεται ένα στοιχείο. Επιστρέφει ένα αντιπρόσωπο κλάσης που ανήκει το στοιχείο.  Έχοντας δύο στοιχεία και χρησιμοποιώντας την λειτουργία find(x,y) σε δύο στοιχεία μπορούμε να δούμε αν τα δύο στοιχεία βρίσκονται στο ίδιο υποσύνολο / κλάση.
 Union (ένωση): Ένωση δύο υποσυνόλων/κλάσεων σε ένα υποσύνολο/κλάση.

Η βασική ιδέα είναι ότι ένα σύνολο "σύμπαν" διαμερίζεται σε υποσύνολα "κλάσεις"  οι οποίες μεταβάλλοντα χρησιμοποιώντας την λειτουργία της ένωσης union''.

Εφαρμογές

Μια δομή ξένων συνόλων χρησιμοποιείται σε λύσεις πολλών προβλημάτων όπως :

 Ανάλυση συνδεσιμότητας σε ένα δίκτυο δεδομένων. 
 Σε παιχνίδια όπως το Go ή το Hex.
 Στην επεξεργασία εικόνας.
 Στο πρόβλημα της διήθησης (Αγγλικά: percolation) υλικών  όπου χρησιμοποιείται η δομή ξένων συνόλων σε προσομοίωση Monte Carlo.
 Στον αλγόρθιμο του Krushkal.

Παραπομπές

Κατηγορία:Δομές δεδομένων