Lecture 11: Union-Find
CSC 226: Algorithms and Data Structures II Quinton ’s Algorithm Pseudocode
𝑲𝒓𝒖𝒔𝒌𝒂𝒍𝑴𝑺𝑻(𝑮):
Input: A weighted connected graph 𝑮 with 𝒏 vertices and 𝒎 edges Output: An MST 𝑻 for 𝑮
Copyright By PowCoder代写 加微信 powcoder
Data structures: Disjoint set 𝑪 maintaining connected components, Priority Queue 𝑸 of edges, and Tree 𝑻
for each vertex 𝒖 in 𝑮 do
𝑪(𝒖) ← {𝒖} // 𝑪(𝒖) denotes the connected component containing 𝒖
Let 𝑸 be a min priority queue storing all edges in 𝑮 by weight 𝑻←∅
while 𝑻 has less than 𝒏 − 𝟏 edges do
𝑶 𝒎 log 𝒎 but we can make this 𝑶 𝒎
𝒖,𝒗 ←𝑸.𝒓𝒆𝒎𝒐𝒗𝒆𝑴𝒊𝒏() Let 𝒖 ∈ 𝑪 𝒖
if𝑪𝒖 ≠𝑪𝒗 then
Add edge 𝒖,𝒗 to 𝑻
Union𝑪 𝒖 and𝑪 𝒗 return 𝑻
How do we implement this disjoint set efficiently such that this takes 𝑶 𝒎 log 𝒏 ?
Implementing Kruskal’s Algorithm
We need to solve two problems to efficiently implement Kruskal’s algorithm:
• Efficiently constructing (inserting all edges into) the priority queue: bottom-up heap • Efficientcycledetection:union-find(disjoint-set)datastructure
Disjoint-Set Data Structure (Union-Find)
Given a set of elements, it is often useful to break them up (partition them) into a number of separate, non-overlapping sets
A disjoint-set is a data structure that keeps track of such a partitioning. There are three operations on disjoint-sets:
• 𝑴𝒂𝒌𝒆𝑺𝒆𝒕: Creates a set containing a single given element
𝟎𝟏𝟐𝟑𝟒𝟓𝟔𝟕𝟖𝟗
Disjoint-Set Data Structure (Union-Find)
Given a set of elements, it is often useful to break them up (partition them) into a number of separate, non-overlapping sets
A disjoint-set is a data structure that keeps track of such a partitioning.
There are three operations on disjoint-sets:
• 𝑴𝒂𝒌𝒆𝑺𝒆𝒕: Creates a set containing a single given element
• 𝑼𝒏𝒊𝒐𝒏: Combine or merge two sets into a single set
Disjoint-Set Data Structure (Union-Find)
Given a set of elements, it is often useful to break them up (partition them) into a number of separate, non-overlapping sets
A disjoint-set is a data structure that keeps track of such a partitioning.
There are three operations on disjoint-sets:
• 𝑴𝒂𝒌𝒆𝑺𝒆𝒕: Creates a set containing a single given element
• 𝑼𝒏𝒊𝒐𝒏: Combine or merge two sets into a single set
• 𝑭𝒊𝒏𝒅: Determine which set a particular element is in. Also used for determining if two elements are in the same set.
𝑪 𝟕 ≠ 𝑪(𝟖)
Disjoint-Set Data Structure (Union-Find)
• The universe consists of 𝒏 elements, named 𝟎, 𝟏, … , 𝒏 − 𝟏
• The data structure is a collection of sets of elements
• Each element is in exactly one set
• Sets are disjoint
• To start, each set contains one element
• Each set has a name
• Usually is the name of any one of its elements
• e.g.𝑪𝟎 =𝑪𝟑 =𝟎,𝑪𝟕 =𝟕,𝑪𝟖 =𝑪𝟗 =𝟗
𝑪 𝟕 ≠ 𝑪(𝟖)
Disjoint Set Operations
• 𝑭𝒊𝒏𝒅 𝒆𝒍𝒆𝒎𝒆𝒏𝒕𝑵𝒂𝒎𝒆
• Returns the name of the unique set that contains the given element
• E.g.𝑭𝒊𝒏𝒅 𝟎 =𝟎,𝑭𝒊𝒏𝒅 𝟐 =𝟎,𝑭𝒊𝒏𝒅 𝟓 =𝟓,𝑭𝒊𝒏𝒅 𝟖 =𝟗,𝑭𝒊𝒏𝒅 𝟗 =𝟗
• 𝑼𝒏𝒊𝒐𝒏 𝒔𝒆𝒕𝑵𝒂𝒎𝒆𝟏,𝒔𝒆𝒕𝑵𝒂𝒎𝒆𝟐
• Merges two sets and replaces them with one
• E.g.𝑼𝒏𝒊𝒐𝒏 𝟓,𝟔 = 𝟓:{𝟓,𝟔},𝑼𝒏𝒊𝒐𝒏 𝟎,𝟗 = 𝟎:{𝟎,𝟏,𝟐,𝟑,𝟒,𝟖,𝟗}
• Time complexity analysis: Involves analyzing the amortized worst-case running time over a sequence of find and union operations
Disjoint Set Implementation 1: Linked List
Create a linked list for each set and choose the element at the head of the list as the set name • 𝑴𝒂𝒌𝒆𝑺𝒆𝒕: Creates a list of one element
• 𝑼𝒏𝒊𝒐𝒏: Append two lists (𝑶 𝟏 )
• 𝑭𝒊𝒏𝒅: Search for list containing element (𝑶(𝒏))
A sequence of 𝒎 union-find operations take 𝑶(𝒎𝒏) time. The amortized time per operation is 𝑶(𝒏).
How should we represent disjoint sets?
• Each set is a rooted tree
• Each element of a set corresponds to a node in a tree
• Canonical element (i.e. name of set) is the root of the tree
We will explore 3 increasingly better ways of implementing disjoint sets 1. Quick-Find
2. Quick-Union
3. Weighted Quick-Union
Quick-Find
Data structure implementation:
• Integerarray𝒊𝒅[]oflength𝒏
• 𝒊𝒅[𝒆] is the name of the set / component containing element 𝒆
𝟖𝟗 and 𝒊𝒅 𝒗
𝑼𝒏𝒊𝒐𝒏(𝒖, 𝒗): To merge components containing 𝒖 and 𝒗, change all entries whose 𝒊𝒅 value equals 𝒊𝒅[𝒖] to 𝒊𝒅[𝒗]
𝒊𝒅[] 𝟎 𝟏 𝟏 𝟖 𝟖 𝟎 𝟎 𝟏 𝟖 𝟖
0123456789 𝑭𝒊𝒏𝒅(𝒆): Look at 𝒊𝒅 𝒆
𝟓𝟔𝟕 • To determine if 𝒖 and 𝒗 are in the same set / component, compare 𝒊𝒅 𝒖
e.g.𝑼𝒏𝒊𝒐𝒏 𝟓,𝟐 :
𝒊𝒅[] 𝟏 𝟏 𝟏 𝟖 𝟖 𝟏 𝟏 𝟏 𝟖 𝟖
0123456789
Quick-Find Time Complexity
𝒊𝒅[] 𝟎 𝟏 𝟏 𝟖 𝟖 𝟎 𝟎 𝟏 𝟖 𝟖
0123456789
• Initialization: 𝑶 𝒏
• Union: 𝑶 𝒏
• Find: 𝑶(𝟏)
• Same Component: 𝑶 𝟏
The union operation is too slow.
A sequence of 𝒏 union operations takes 𝑶 𝒏𝟐
Quick-Union
Data structure implementation:
• Integerarray𝒊𝒅[]oflength𝒏
• 𝒊𝒅[𝒆] is the parent of element 𝒆
𝒊𝒅[] 𝟎 𝟏 𝟗 𝟒 𝟗 𝟔 𝟔 𝟕 𝟖 𝟗
0123456789 • Therootof𝒆is𝒊𝒅 𝒊𝒅 𝒊𝒅 …𝒊𝒅 𝒆 …
• The root is the name of the set / component containing 𝒆
• A root 𝒓 of a component is indicated when the 𝒊𝒅 𝒓 = 𝒓
𝒊𝒅[] 𝟎 𝟏 𝟗 𝟒 𝟗 𝟔 𝟔 𝟕 𝟖 𝟗
0123456789
Quick-Union
Data structure implementation:
• Integerarray𝒊𝒅[]oflength𝒏
• 𝒊𝒅[𝒆] is the parent of element 𝒆
𝒊𝒅[] 𝟎 𝟏 𝟗 𝟒 𝟗 𝟔 𝟔 𝟕 𝟖 𝟗
0 1 2 3 4 5 6 7 8 9
• Therootof𝒆is𝒊𝒅 𝒊𝒅 𝒊𝒅 …𝒊𝒅 𝒆 …
• The root is the name of the set / component containing 𝒆
• A root 𝒓 of a component is indicated when the 𝒊𝒅 𝒓 = 𝒓 𝑭𝒊𝒏𝒅(𝒆): Look for the root of 𝒆
• To determine if 𝒖 and 𝒗 are in the same set / component, compare 𝒊𝒅 of 𝒖’s root to 𝒊𝒅 of 𝒗’s root
𝑼𝒏𝒊𝒐𝒏(𝒖, 𝒗): To merge components containing 𝒖 and 𝒗, set the 𝒊𝒅 of 𝒖’s root to 𝒊𝒅 of 𝒗’s root
• Only need to change one value 𝟔
e.g.𝑼𝒏𝒊𝒐𝒏𝟓,𝟐: 𝒊𝒅[] 𝟎 𝟏 𝟗 𝟒 𝟗 𝟔 𝟔 𝟕 𝟖 𝟔 0123456789 𝟐𝟒
Quick-Union Time Complexity
𝒊𝒅[] 𝟎 𝟏 𝟏 𝟖 𝟖 𝟎 𝟎 𝟏 𝟖 𝟖
0123456789 𝟐𝟒𝟓
• Initialization: 𝑶 𝒏
• Union: 𝑶 𝒏 // includes cost of finding roots • Find: 𝑶(𝒏)
• Same Component: 𝑶 𝒏
Trees created can get tall, which makes it slow to find the root. The find operation can get too slow.
Quick-Union Time Complexity
𝟖 𝒊𝒅[] 𝟏 𝟐 𝟑 𝟒 𝟓 𝟔 𝟕 𝟖 𝟗 𝟗 𝟕
0123456789
• Initialization: 𝑶 𝒏
• Union: 𝑶 𝒏 // includes cost of finding roots • Find: 𝑶(𝒏)
• Same Component: 𝑶 𝒏
Trees created can get tall, which makes it slow to find the root. The find operation can get too slow.
𝟔 𝟓 𝟒 𝟑 𝟐 𝟏 𝟎
Improving Quick-Union
We can modify quick-union to avoid tall trees to make union and find operations faster.
𝒊𝒅[] 𝟖 𝟖 𝟗 𝟒 𝟗 𝟔 𝟔 𝟓 𝟖 𝟔
0123456789 𝟐𝟒𝟕𝟖
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com