Union-find Data Structure for Disjoint Sets
In this tutorial, you will learn about the union-find data structure, which is used for managing disjoint sets. The tutorial covers the concepts of union and find operations, as well as the idea of using a forest of trees to represent groups. By following the examples provided, you will understand how to perform union and find operations efficiently, maintaining the structure of disjoint sets. The tutorial also explains the heuristic used to optimize the union operation by balancing the heights of trees. Get hands-on experience with union-find in action and learn how to determine the root of a group effectively.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CSCI 3160 Design and Analysis of Algorithms Tutorial 3 Chengyu Lin
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 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 1 D 1 B C E
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 0 C 0 E 0 B 0 D 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 1 C 0 E 0 B 0 D 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 1 C 1 E 0 B 0 D 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 2 C 1 E 0 B 0 D 0
Your turn Find(C)? A 2 C 1 E 0 B 0 D 0
Your turn Find(C)? o Find(C) returns A A 2 C 1 E 0 B 0 D 0
Your turn Union(B, E)? A 2 C 1 E 0 B 0 D 0
Your turn Union(B, E)? o Find(B) returns A and Find(E) returns E o Make Alice the boss of Eve o No increase in the tree height (Why?) A 2 C 1 E 0 B 0 D 0
Final result Does this look more like a tree? 2 A C 1 E 0 B 0 D 0
Analysis Height of each tree = O(log n) Cost of Find(): O(log n) Cost of Union(): O(log n) o Dominated by the cost of Find()
Minimum spanning tree G = (V, E): undirected, connected, (non- negatively) weighted Problem: find a subset of edges with minimum total weight such that all vertices in V are connected using these edgesA 1 B 4 5 3 6 C D E 2 7 Total weight = 1 + 2 + 3 + 6 = 12
Kruskals algorithm In words: o Sort the edges in ascending order of weights o Initialize: set T = o While T is not a spanning tree Consider the next edge in the sorted list If adding it to T does not cause a cycle, add it The union-find structure helps us check for cycles o Adding an edge corresponds to putting the two endpoints into the same group o Connecting two vertices in the same group causes a cycle
Dry run 1: Sort the edges Edge Weight (A, B) 1 (C, D) 2 (B, D) 3 (A, C) 4 1 B A (A, D) 5 4 5 3 6 (B, E) 6 (D, E) 7 C D E 2 7
Dry run 2: Set T = B A Edge Weight (A, B) 1 (C, D) 2 C D E (B, D) 3 (A, C) 4 1 B A (A, D) 5 4 5 3 6 (B, E) 6 (D, E) 7 C D E 2 7
Dry run 3: Consider the first edge B A Edge Weight (A, B) 1 (C, D) 2 C D E (B, D) 3 (A, C) 4 1 B A (A, D) 5 4 5 3 6 (B, E) 6 (D, E) 7 C D E 2 7
Dry run 4: Consider the second edge B A Edge Weight (A, B) 1 (C, D) 2 C D E (B, D) 3 (A, C) 4 1 B A (A, D) 5 4 5 3 6 (B, E) 6 (D, E) 7 C D E 2 7
Dry run 5: Consider the third edge B A Edge Weight (A, B) 1 (C, D) 2 C D E (B, D) 3 (A, C) 4 1 B A (A, D) 5 4 5 3 6 (B, E) 6 (D, E) 7 C D E 2 7
Dry run 6: B A Edge Weight (A, B) 1 (C, D) 2 C D E (B, D) 3 (A, C) 4 1 B A (A, D) 5 4 5 3 6 (B, E) 6 (D, E) 7 C D E 2 7
Dry run 7: B A Edge Weight (A, B) 1 (C, D) 2 C D E (B, D) 3 (A, C) 4 1 B A (A, D) 5 4 5 3 6 (B, E) 6 (D, E) 7 C D E 2 7
Dry run 8: B A Edge Weight (A, B) 1 (C, D) 2 C D E (B, D) 3 (A, C) 4 1 B A (A, D) 5 4 5 3 6 (B, E) 6 (D, E) 7 C D E 2 7
Dry run 9: We have find an MST! B A Edge Weight (A, B) 1 (C, D) 2 C D E (B, D) 3 (A, C) 4 1 B A (A, D) 5 4 5 3 6 (B, E) 6 (D, E) 7 C D E 2 7
Analysis Correctness o In each step, we keep a set of edges T that is a subset of an MST o Theorem: Let S be any tree in the forest (V, T). We can add the lightest edge from S to V-S to T, and the resulting set of edges is also a subset of an MST Space complexity = O(|V|+|E|) Time complexity = O(|E|log|V|) o Sorting alone takes time O(|E|log|V|) (Note that |E| = O(|V|2)) o Cycle checking takes O(log|V|) operations (Find()) o Adding an edge also takes O(log|V|) operations (Union())
Dry run revisited 2: Set T = B A Edge Weight (A, B) 1 (C, D) 2 C D E (B, D) 3 (A, C) 4 (A, D) 5 (B, E) 6 A 0 C 0 E 0 (D, E) 7 B 0 D 0
Dry run revisited 3: Consider the first edge B A Edge Weight (A, B) 1 (C, D) 2 C D E (B, D) 3 (A, C) 4 (A, D) 5 (B, E) 6 A 1 C 0 E 0 (D, E) 7 B 0 D 0
Dry run revisited 4: Consider the second edge B A Edge Weight (A, B) 1 (C, D) 2 C D E (B, D) 3 (A, C) 4 (A, D) 5 (B, E) 6 A 1 C 1 E 0 (D, E) 7 B 0 D 0
Dry run revisited 5: Consider the third edge B A Edge Weight (A, B) 1 (C, D) 2 C D E (B, D) 3 (A, C) 4 (A, D) 5 (B, E) 6 A 2 C 1 E (D, E) 7 B 0 D 0 0
Dry run revisited 6: B A Edge Weight (A, B) 1 (C, D) 2 C D E (B, D) 3 (A, C) 4 (A, D) 5 (B, E) 6 A 2 C 1 E (D, E) 7 B 0 D 0 0
Dry run revisited 7: B A Edge Weight (A, B) 1 (C, D) 2 C D E (B, D) 3 (A, C) 4 (A, D) 5 (B, E) 6 A 2 C 1 E (D, E) 7 B 0 D 0 0
Dry run revisited 8: B A Edge Weight (A, B) 1 (C, D) 2 C D E (B, D) 3 (A, C) 4 (A, D) 5 (B, E) 6 A 2 C 1 E 0 (D, E) 7 B 0 D 0
Dry run revisited 9: We have find an MST! B A Edge Weight (A, B) 1 (C, D) 2 C D E (B, D) 3 (A, C) 4 (A, D) 5 (B, E) 6 A 2 C 1 E 0 (D, E) 7 B 0 D 0
End Questions
