Система непересекающихся множеств

Система непересекающихся множеств это структура данных (также называемая структурой данной поиска пересечения или множеством поиска слияния), которая управляет множеством элементов, разбитых на несколько непересекающихся подмножеств. Она предоставляет около-константное время выполнения операций (ограниченное обратной функцией Акерманна) по добавлению новых множеств, слиянию существующих множеств и опеределению, относятся ли элементы к одному и тому же множеству.

Применяется для хранения компонент связности в графах, в частности, алгоритму Краскала необходима подобная структура данных для эффективной реализации.

Основные операции:

• MakeSet(x) - создаёт одноэлементное множество {x},
• Find(x) - возвращает идентификатор множества, содержащего элемент x,
• Union(x,y) - объединение множеств, содержащих x и y.

После некоторых операций объединения, некоторые множества собраны вместе

Ссылки

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