Disjoint Sets Part 1 Data Structures for Disjoint Sets A disjoint set data structure maintains a collection set of disjoint dynamic sub sets S S1 S2 Sk Each element x of a set could be a pointer to an object possibly with multiple fields Representative of a set We choose one element of a set to identify the set e g we use the root of a tree to identify a tree or the head element of a linked list to access the linked list Note that the representative is an element in the set Why Disjoint Sets The universe is composed of many disjoint sets An element belongs to a unique set Given an element we need to find the set it belongs to Given two elements we need to decide whether they Given two disjoint sets we may need to replace them are in the same set by their union Operations on Disjoint Sets Make Set x Union x y Find Set x creates a new set whose only member is x Obviously x is the representative replaces the two sets Sx and Sy that contain elements x and y by their union Sets are assumed to be disjoint no element overlap The representative of Sx or Sy becomes the representative of the united set returns the pointer to the representative of the unique set containing x Application Finding Connected Components Connected Components G 1 2 3 4 5 for each vertex v V G do Make Set v for each edge u v E G do if Find Set u Find Set v then Union u v a b c d e f g h i edge processed initial sets a b c collection of disjoint sets g e d f h i Application Finding Connected Components Connected Components G 1 2 3 4 5 for each vertex v V G do Make Set v for each edge u v E G do if Find Set u Find Set v then Union u v a b c d e f g h i edge processed initial sets a b b c c collection of disjoint sets g g e e d d f f a a b h h i i Application Finding Connected Components Connected Components G 1 2 3 4 5 for each vertex v V G do Make Set v for each edge u v E G do if Find Set u Find Set v then Union u v a b c d e f g h i edge processed initial sets a b a c b c c collection of disjoint sets g g g e e e d d d f f f a a b a b c h h h i i i Application Finding Connected Components Connected Components G 1 2 3 4 5 for each vertex v V G do Make Set v for each edge u v E G do if Find Set u Find Set v then Union u v a b c d e f g h i edge processed initial sets a b a c b c b c c collection of disjoint sets g g g a a b a b c Find Set b Find Set c e e e d d d f f f h h h i i i Application Finding Connected Components Connected Components G 1 2 3 4 5 for each vertex v V G do Make Set v for each edge u v E G do if Find Set u Find Set v then Union u v a b c d e f g h i edge processed initial sets a b a c b c d e b c c collection of disjoint sets g g g a a b a b c Find Set b Find Set c a b c d e e e e d d d f f f g f h h h i i i h i Application Finding Connected Components Connected Components G 1 2 3 4 5 for each vertex v V G do Make Set v for each edge u v E G do if Find Set u Find Set v then Union u v a b c d e f g h i edge processed initial sets a b a c b c d e d g b c c collection of disjoint sets g g g a a b a b c Find Set b Find Set c a b c d e d e g a b c e e e d d d f f f g f f h h h h h i i i i i Application Finding Connected Components Connected Components G 1 2 3 4 5 for each vertex v V G do Make Set v for each edge u v E G do if Find Set u Find Set v then Union u v a b c d e f g h i edge processed initial sets a b a c b c d e d g e f b c c collection of disjoint sets g g g e e e d d d a a b a b c Find Set b Find Set c a b c d e d e g a b c a b c d e g f g f f f f f h h h h h h i i i i i i Application Finding Connected Components Connected Components G 1 2 3 4 5 for each vertex v V G do Make Set v for each edge u v E G do if Find Set u Find Set v then Union u v a b c d e f g h i edge processed initial sets a b a c b c d e d g e f e g b c c collection of disjoint sets g g g e e e d d d f f f a a b a b c Find Set b Find Set c a b c d e d e g a b c a b c d e g f Find Set e Find Set g g f f h h h h h h i i i i i i Application Finding Connected Components Connected Components G 1 2 3 4 5 for each vertex v V G do Make Set v for each edge u v E G do if Find Set u Find Set v then Union u v a b c d e f g h i edge processed initial sets a b a c b c d e d g e f e g h i b c c collection of disjoint sets g g g e e e d d d f f f a a b a b c Find Set b Find Set c d e a b c a b c d e g a b c d e g f Find Set e Find Set g a b c d e g f f f g h h h h h h i i i i …
View Full Document
Unlocking...