Система непересічних множин

Система множин, що не перетинаються(англ. disjoint-set, або union-find data structure) - структура даних, яка дозволяє адмініструвати безліч елементів, розбите на непересічні підмножини. При цьому кожному підмножині призначається його представник - елемент цього підмножини. Абстрактна структура даних визначається безліччю трьох операцій: < U n i o n , F i n d , M a k e S e t > ,\mathrm ,\mathrm \>> .

Застосовується для зберігання компонент зв'язності в графах, зокрема алгоритму Фарбала необхідна подібна структура даних для ефективної реалізації.

Зміст

Тривіальна реалізація зберігає приналежність елементів S і представників r i > у індексному масиві. Насправді ж частіше використовуються безлічі дерев. Це дозволяє істотно скоротити час, необхідний операції Find . У цьому представник записується в корінь дерева, інші елементи класу у вузли під нею.

Для прискорення операцій Union і Find можуть бути використані евристики Union-By-Size, Union-By-Height, Random-Union та стиснення шляхів.

Евристика Union-By-Height аналогічна Union-By-Size, але використовує висоту дерева замість розміру.

---