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

Система неперетинних множин це структура даних (також звана структурою даної пошуку перетину або безліччю пошуку злиття), яка управляє безліччю елементів, розбитих на кілька підмножин, що не перетинаються. Вона надає близько-константний час виконання операцій (обмежений зворотною функцією Акерманна) за додаванням нових множин, *злиття існуючих множин і *випередження, чи відносяться елементи до одного і того ж безлічі.

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

Основні операції:

• MakeSet(x) - створює одноелементне безліч {x},
• Find(x) - повертає ідентифікатор множини, що містить елемент x,
• Union(x,y) - об'єднання множин, що містять x та y.

Після деяких операцій об'єднання, деякі множини зібрані разом.

Посилання

• СНМ на Wikipedia
• СНМ на YouTube