Union Find
June 24, 2025
04:32 AM
Loading content...
Định nghĩa
Union Find (DSU) là một cấu trúc dữ liệu được sử dụng phổ biến để kiểm tra chu trình trong đồ thị vô hướng. Cơ chế kiểm tra chu trình dựa trên ý tưởng về tập hợp các đỉnh liên thông.
Nguyên lý hoạt động:
(u, v) ta kiểm tra xem hai đỉnh u và v có thuộc cùng một tập hợp hay không (bằng hàm find )(u, v) sẽ tạo thành một chu trình, vì ta có thể đi từ u -> v qua các cạnh đã có, rồi lại quay về u qua cạnh mớiunion ) và tiếp tục xét các cạnh tiếp theoLý do kiểm tra được chu trình
Minh họa
Dưới đây là ví dụ dry run minh họa cách Union-Find kiểm tra chu trình trong đồ thị vô hướng, thể hiện sự thay đổi của mảng parent và rank sau từng bước khi xét các cạnh. Đồ thị gồm 4 đỉnh (0, 1, 2, 3) và các cạnh: (0,1), (1,2), (2,3), (3,1). Cạnh cuối cùng sẽ tạo chu trình.
Dry run minh họa Union-Find kiểm tra chu trình trong đồ thị vô hướng:
1Bước 1: Xét cạnh (0, 1)
2Trước khi union:
3 parent = [0, 1, 2, 3]
4 rank = [0, 0, 0, 0]
5Sau khi union:
6 parent = [0, 0, 2, 3]
7 rank = [1, 0, 0, 0]
8
9Bước 2: Xét cạnh (1, 2)
10Trước khi union:
11 parent = [0, 0, 2, 3]
12 rank = [1, 0, 0, 0]
13Sau khi union:
14 parent = [0, 0, 0, 3]
15 rank = [1, 0, 0, 0]
16
17Bước 3: Xét cạnh (2, 3)
18Trước khi union:
19 parent = [0, 0, 0, 3]
20 rank = [1, 0, 0, 0]
21Sau khi union:
22 parent = [0, 0, 0, 0]
23 rank = [1, 0, 0, 0]
24
25Bước 4: Xét cạnh (3, 1)
26Trước khi union:
27 parent = [0, 0, 0, 0]
28 rank = [1, 0, 0, 0]
29Sau khi union:
30 parent = [0, 0, 0, 0]
31 rank = [1, 0, 0, 0]
32=> Phát hiện chu trình khi thêm cạnh này!Ở bước 4, khi xét cạnh (3, 1) cả hai đỉnh đều đã thuộc cùng một tập hợp (có cùng parent ) nên việc thêm cạnh này sẽ tạo thành chu trình
Các khái niệm chính trong Union-Find:
Kỹ thuật tối ưu hóa:
Time and space complexity:
Implement using typescript
1class UnionFind {
2 private parent: number[];
3 private rank: number[];
4
5 constructor(size: number) {
6 this.parent = Array.from({length: size}, (_, i) => i);
7 this.rank = Array(size).fill(0);
8 }
9
10 find(node: number): number {
11 if(this.parent[node] !== node) {
12 this.parent[node] = this.find(this.parent[node]) // path compression
13 }
14 return this.parent[node]
15 }
16
17 union(nodeA: number, nodeB: number): boolean {
18 const rootA = this.find(nodeA);
19 const rootB = this.find(nodeB);
20
21 if(rootA === rootB) return false;
22
23 if(this.rank[rootA] > this.rank[rootB]) {
24 this.parent[rootB] = rootA;
25 } else if (this.rank[rootA] < this.rank[rootB]) {
26 this.parent[rootA] = rootB;
27 } else {
28 this.parent[rootB] = rootA;
29 this.rank[rootA]++;
30 }
31
32 return true;
33 }
34}