Informații generale
Un sistem de seturi disjuncte, uneori o uniune-find, este o structură specifică de date care conține informații despre un set de seturi care vă permite să combinați seturi și să răspundeți la întrebarea dacă aceste elemente aparțin aceluiași set.
Inițial, sunt luate în considerare diferite elemente diferite, fiecare dintre ele fiind un set independent. Apoi, oricare două seturi pot fi combinate și toate elementele celor două seturi devin elemente ale setului de rezultate. Evident, din starea inițială (N dintr-un singur element) prin fuziunea (N-1), se va obține o stare în care toate elementele sunt combinate într-un set. După cum se poate observa în continuare, este suficient să se completeze pur și simplu implementarea unui sistem de seturi disjuncte cu operarea adăugării unui nou set de elemente (adică adăugarea unui element (N + 1) care formează un set independent).
Orice set poate fi identificat în mod unic utilizând unul dintre elementele sale: două seturi nu pot conține definitiv același element (acest fapt este reflectat de cuvântul "disjoint" în numele structurii de date). Un astfel de element este numit reprezentantul setului (element reprezentativ englez).
În continuare, vom presupune că elementele seturilor sunt numere întregi. Un sistem de seturi disjuncte trebuie să asigure următoarele operațiuni:
- definiția reprezentantului setului din care face parte elementul x. Evident, dacă elementele x și y aparțin aceluiași set, atunci trebuie găsită condiția find (x) == find (y). În caz contrar, trebuie să existe o căutare (x)! = Find (y);
Articole similare
Trimiteți-le prietenilor: