Tập hợp rời rạc là một cấu trúc dữ liệu theo dõi một tập hợp các phần tử được phân chia thành nhiều tập hợp con rời rạc [không chồng chéo]. Nói cách khác, một tập hợp rời rạc là một nhóm các tập hợp trong đó không có phần tử nào có thể nằm trong nhiều hơn một tập hợp. Nó còn được gọi là cấu trúc dữ liệu hợp-tìm vì nó hỗ trợ thao tác hợp và tìm trên các tập con. Hãy bắt đầu bằng cách xác định chúng
Tìm. Nó xác định phần tử cụ thể nằm trong tập hợp con nào và trả về đại diện của tập hợp cụ thể đó. Một mục từ bộ này thường đóng vai trò là "đại diện" của bộ.
Liên minh. Nó hợp nhất hai tập hợp con khác nhau thành một tập hợp con duy nhất và đại diện của tập hợp này trở thành đại diện của tập hợp khác.
Tập hợp rời rạc cũng hỗ trợ một thao tác quan trọng khác có tên là MakeSet , tạo một tập hợp chỉ chứa một phần tử đã cho trong đó.
Union–Find hoạt động như thế nào?
Chúng ta có thể xác định xem hai phần tử có thuộc cùng một tập con hay không bằng cách so sánh kết quả của hai thao tác Tìm. Nếu hai phần tử thuộc cùng một tập hợp thì chúng có cùng cách biểu diễn; . Nếu hợp được gọi trên hai phần tử, hợp nhất hai tập hợp con mà hai phần tử đó thuộc về
Làm thế nào để thực hiện các bộ rời rạc?
Rừng tập hợp rời rạc là cấu trúc dữ liệu trong đó mỗi tập hợp được biểu thị bằng một dữ liệu dạng cây trong đó mỗi nút chứa tham chiếu đến cha của nó và đại diện của mỗi tập hợp là gốc của .
- Find đi theo các nút cha cho đến khi tới nút gốc.
- Union kết hợp hai cây thành một bằng cách gắn gốc của cây này vào gốc của cây kia.
Ví dụ, xem xét năm tập hợp khác nhau S1, S2, S3, S4 và S5 được biểu diễn bằng một cây, như sơ đồ bên dưới. Mỗi tập hợp ban đầu chỉ chứa một phần tử, vì vậy con trỏ cha của chúng trỏ tới chính nó hoặc NULL
S1 = {1}, S2 ={2}, S3 = {3}, S4 ={4} and S5 = {5}
Phép toán Find trên phần tử i sẽ trả về đại diện của Si, trong đó S20, i. e. , S21
Nếu chúng ta thực hiện S22, thì S3 và S4 sẽ được hợp nhất thành một tập hợp rời rạc, S3. Bây giờ,
S26
S27 sẽ trả về đại diện của tập hợp S3, i. e. , S29
Nếu chúng ta thực hiện S30, thì S1 và S2 sẽ được hợp nhất thành một tập hợp rời rạc, S1. Bây giờ,
S34
S35 hoặc S36 sẽ trả về đại diện của tập hợp S1, i. e. , S38
Nếu chúng ta thực hiện S39, thì S3 và S1 sẽ được hợp nhất thành một tập hợp rời rạc, S3. Bây giờ,
S43
Một cách để thực hiện những điều này có thể là
function MakeSet[x]
x. parent = x
function Find[x]
if x. parent == x
return x
else
return Find[x. parent]
hàm Union[x, y]
xRoot = Find[x]
yRoot = Find[y]
xRoot.parent = yRoot
Sau đây là triển khai C++, Java và Python của union–find sử dụng bảng băm để triển khai một tập hợp rời rạc
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include
#include
#include
sử dụng không gian tên std;
// Một lớp đại diện cho một tập hợp rời rạc
lớp DisjointSet
{
unordered_map parent;
công khai.
// thực hiện thao tác MakeSet
void makeSet[vector const &universe]
{
// tạo `n` bộ rời rạc [mỗi bộ một mục]
cho [int i: vũ trụ] {
cha mẹ[i] = i;
}
}
// Tìm gốc của tập hợp chứa phần tử `k`
int Tìm[int k]
{
// nếu `k` là gốc
nếu [cha mẹ[k] == k] {
return k;
}
// lặp lại cho cấp độ gốc cho đến khi chúng tôi tìm thấy thư mục gốc
trả về Tìm[cha[k]];
}
// Thực hiện phép hợp hai tập con
vô hiệu Liên minh[int a, int b]
{
// tìm nghiệm của tập hợp chứa các phần tử `x` và `y`
int x = Tìm[a];
int y = Tìm[b];
cha mẹ[x] = y;
}
};
void printSets[vectơ const &universe, DisjointSet &ds]
{
cho [int i: vũ trụ] {
cout