Δομή ξένων συνόλων (πληροφορική)
Στην πληροφορική, μια δομή ξένων συνόλων (Αγγλικά: disjoint-set data structure, γνωστή και ως union–find δομή ή σύνολο merge–find) είναι μια δομή δεδομένων η οποία χειρίζεται ένα σύνολο στοιχείων τα οποία διαχωρίζονται σε ένα αριθμό μη επικαλυπτόμενων υποσυνόλων (ή κλάσεων). Μια τέτοια δομή υποστηρίζει τις παρακάτω δύο βασικές λειτουργίες:
- Find (εύρεση): Καθορισμός σε ποιο υποσύνολο βρίσκεται ένα στοιχείο. Επιστρέφει ένα αντιπρόσωπο κλάσης που ανήκει το στοιχείο. Έχοντας δύο στοιχεία και χρησιμοποιώντας την λειτουργία find(x,y) σε δύο στοιχεία μπορούμε να δούμε αν τα δύο στοιχεία βρίσκονται στο ίδιο υποσύνολο / κλάση.
- Union (ένωση): Ένωση δύο υποσυνόλων/κλάσεων σε ένα υποσύνολο/κλάση.
Η βασική ιδέα είναι ότι ένα σύνολο "σύμπαν" διαμερίζεται σε υποσύνολα "κλάσεις" οι οποίες μεταβάλλοντα χρησιμοποιώντας την λειτουργία της ένωσης union.[1]
Εφαρμογές Επεξεργασία
Μια δομή ξένων συνόλων χρησιμοποιείται σε λύσεις πολλών προβλημάτων όπως [2]:
- Ανάλυση συνδεσιμότητας σε ένα δίκτυο δεδομένων.
- Σε παιχνίδια όπως το Go ή το Hex.
- Στην επεξεργασία εικόνας.
- Στο πρόβλημα της διήθησης (Αγγλικά: percolation) υλικών [3] όπου χρησιμοποιείται η δομή ξένων συνόλων σε προσομοίωση Monte Carlo.
- Στον αλγόρθιμο του Krushkal.
Παραπομπές Επεξεργασία
- ↑ ∆ . Φωτάκης. «Λεξικό , Union – Find» (PDF). Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών - Εθνικό Μετσόβιο Πολυτεχνείο. Αρχειοθετήθηκε από το πρωτότυπο (PDF) στις 22 Ιανουαρίου 2016. Ανακτήθηκε στις 28 Ιανουαρίου 2015.
- ↑ Sedgewick, Robert. «Union-Find Algorithms» (PDF). University of Princeton. Ανακτήθηκε στις 28 Ιανουαρίου 2015.
- ↑ Τσακίρης, Νικόλας (2011). Θεωρία Δίηθησης και Μεταβολές Φάσης (PDF). Αριστοτέλειο Πανεπιστήμιο Θεσσαλονίκης- Διδακτορική Διατριβή. σελ. 2.