disjoint-set data structure

Angol

Főnév

disjoint-set data structure (tsz. disjoint-set data structures)

1. (informatika) A disjoint-set data structure, magyarul diszjunkt halmazok adatstruktúra (más néven unió-find vagy merge-find struktúra), olyan adatstruktúra, amely hatékonyan kezeli a nem metsződő halmazok gyűjteményét, és támogatja az alábbi két alapműveletet:

---

🔧 Alapműveletek

1. Find(x) – Meghatározza, melyik halmazba tartozik az x elem. → Visszaad egy képviselőt (representative), ami a halmaz azonosítója.
2. Union(x, y) – Összevonja x és y halmazait, amennyiben különbözőek. → Az x és y elemek képviselői egyesülnek.

---

🎯 Alkalmazások

• Gráf algoritmusokban (pl. Kruskal algoritmus a minimális feszítőfához)
• Képfeldolgozásban (pl. régiók összekapcsolása)
• Dinamikus összefüggésvizsgálat (pl. csoporttagság, hálózati összeköttetés)
• Hálózatmodellezés (pl. klikkek, komponensek kezelése)

---

🧠 Implementáció – Fa reprezentáció

A diszjunkt halmazokat gyökérfa-struktúrával reprezentálják:

• Minden elem mutat a szülőjére.
• A gyökér az a képviselő, amely önmagára mutat.
• A find(x) rekurzívan halad felfelé a fában.

---

⚙️ Optimalizálási technikák

1. Path Compression (útvonal-tömörítés)

A find(x) művelet során az x és minden őse közvetlenül a gyökérhez lesz kötve, így a későbbi find műveletek gyorsabbak lesznek.

2. Union by Rank / Size

A union(x, y) során a kisebb mélységű/elemszámú fát kapcsolják a nagyobbhoz, így elkerülhető a túlmély fa.

👉 A fenti két technika kombinációjával a műveletek átlagos futási ideje közelít az inverz Ackermann-függvényhez, ami kvázi-konstans idő.

---

🧪 Példa

int parent[MAX];  // Minden elemhez egy szülő

// Inicializálás
void makeSet(int n) {
    for (int i = 0; i < n; ++i)
        parent[i] = i;
}

// Find művelet path compression-nel
int find(int x) {
    if (parent[x] != x)
        parent[x] = find(parent[x]);
    return parent[x];
}

// Union művelet
void unionSets(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY)
        parent[rootY] = rootX;
}

---

✅ Összefoglalás

A disjoint-set data structure kulcsfontosságú eszköz összefüggésvizsgálathoz és klaszterezéshez, különösen gráfalgoritmusokban. A find és union műveletek hatékony optimalizálása révén nagy adathalmazokon is gyors és skálázható megoldásokat tesz lehetővé.

További információk

• disjoint-set data structure - Szótár.net (en-hu)
• disjoint-set data structure - Sztaki (en-hu)
• disjoint-set data structure - Merriam–Webster
• disjoint-set data structure - Cambridge
• disjoint-set data structure - WordNet
• disjoint-set data structure - Яндекс (en-ru)
• disjoint-set data structure - Google (en-hu)
• disjoint-set data structure - Wikidata
• disjoint-set data structure - Wikipédia (angol)