Thursday, June 14, 2012

Disjoint Sets

Disjoint set is a mathematical term which represents sets among which no two set has any item common. So intersection od any two sets results to empty set.

Operations


Union


Merges two sets into one set.

 

Find


Given an item it returns the set identifier in which the item belongs.


List based disjoint set


 

Tree based disjoint set


Path compression


Union by size


Implementing quick union using Array



[incomplete]

No comments:

Post a Comment