An eager representation of a disjoint-set data structure that stores each member's current representative directly. Finding a representative is direct when keys are array indices; arbitrary keys in a parallel key array can add a linear search. A disjoint-set union operation scans members and replaces every occurrence of one old representative with the other. The representative labels must be snapshotted before this scan. Its easy abstraction function contrasts with the parent-pointer representation of a disjoint-set forest.
Articles by others on the same topic
There are currently no matching articles.