CSCI 3160 Design and Analysis of Algorithms Tutorial 3 Chengyu Lin ● ●
CSCI 3160 Design and Analysis of Algorithms Tutorial 3 Chengyu Lin
Outline Union-find data structure Minimum spanning tree (MST) ·Kruskal''s algorithm ● ●
Outline • Union-find data structure • Minimum spanning tree (MST) • Kruskal’s algorithm
Union-find A data structure for disjoint sets n number of members,forming disjoint groups Two members are in the same group if and only if they have a common leader 。Operations: o Union:merge two groups o Find:name the leader of the group We do not really care about who the leader is;we only want to tell one group from another ●
Union-find • A data structure for disjoint sets • n = number of members, forming disjoint groups • Two members are in the same group if and only if they have a common leader • Operations: o Union: merge two groups o Find: name the leader of the group • We do not really care about who the leader is; we only want to tell one group from another
Union-find Idea:use a forest (collection of trees) o a group→a free o leader-root of the tree 。Example: o Group 1:Alice,Bob o Group 2:Carol,Dave,Eve Store the height of each tree A 1 D 1 at the root B C E ● ●
Union-find • Idea: use a forest (= collection of trees) o a group → a tree o leader → root of the tree • Example: o Group 1: Alice, Bob o Group 2: Carol, Dave, Eve • Store the height of each tree at the root A B C D E 1 1
Union-find Find:return the root of the group Union:make the leader of one group the boss of the other o Our heuristic:make the root of the shorter tree point to the root of the other tree o If both trees are of the same height h,then the resulting tree has height h+1 ● ●
Union-find • Find: return the root of the group • Union: make the leader of one group the boss of the other o Our heuristic: make the root of the shorter tree point to the root of the other tree o If both trees are of the same height h, then the resulting tree has height h+1