香港中文大学：《Design and Analysis of Algorithms》课程教学资源（辅导课件）tutorial 03

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

Union-find in action 。Initialize o Everyone is his/her own boss A B D E 0 0 0 0 ●

Union-find in action • Initialize o Everyone is his/her own boss A B C D E 0 0 0 0 0

Union-find in action 。Union(A,B o Find(A)returns A and Find(B)returns B o Make Alice the boss of Bob o Increase the height of the tree A B C D E 1 0 0 0 0 ● ●

Union-find in action • Union(A, B) o Find(A) returns A and Find(B) returns B o Make Alice the boss of Bob o Increase the height of the tree A B C D E 1 0 0 0 0

Union-find in action 。Union(C,D) o Find(C)returns C and Find(D)returns D o Make Carol the boss of Dave o Increase the height of the tree X A B C ← D E 1 0 1 0 ● ●

Union-find in action • Union(C, D) o Find(C) returns C and Find(D) returns D o Make Carol the boss of Dave o Increase the height of the tree A B C D E 1 0 1 0 0

Union-find in action 。Union(B,D】 o Find(B)returns A and Find(D)returns C o Make Alice the boss of Carol o Increase the height of the tree B C D E 2 0 ● ●

Union-find in action • Union(B, D) o Find(B) returns A and Find(D) returns C o Make Alice the boss of Carol o Increase the height of the tree A B C D E 2 0 1 0 0

Your turn 。Find(C? A B C D E 2 0 ●

Your turn • Find(C)? A B C D E 2 0 1 0 0