Cấu trúc dữ liệu và Giải thuật Bài 85: Disjoint Set Union (DSU) - Quản lý tập hợp rời rạc và thuật toán Kruskal.

Trong Bài 74 và 75, bạn đã giải quyết các bài toán trên một đồ thị dạng Cây (Tree) tĩnh bằng HLD và Binary Lifting. Tuy nhiên, trong thực tế kỹ thuật tại Hasaki hoặc hệ thống vé tự động (AFC) của tuyến Metro, bạn thường phải đối mặt với đồ thị động — nơi các kết nối giữa các trạm hoặc mạng lưới máy chủ liên tục được thêm vào.

Làm sao để biết Trạm A và Trạm B đã thông mạng với nhau hay chưa? Nếu dùng thuật toán duyệt DFS/BFS mỗi lần kiểm tra, hệ thống sẽ chìm trong vòng lặp $O(N)$ tốn kém. Để xử lý các bài toán "kết nối mạng lưới" này trong thời gian xấp xỉ $O(1)$ , giới khoa học máy tính sử dụng Disjoint Set Union (DSU) — hay còn gọi là Cấu trúc dữ liệu Tìm-và-Hợp (Union-Find).

1. Bản chất của Disjoint Set Union (DSU)

DSU là một cấu trúc dữ liệu duy trì một tập hợp các nhóm (components) rời rạc. Nó hỗ trợ hai thao tác cốt lõi:

Find (Tìm kiếm): Xác định xem một phần tử $X$ đang thuộc nhóm nào. Thường được dùng để kiểm tra xem $X$ và $Y$ có đang cùng chung một nhóm hay không.
Union (Hợp nhất): Gộp nhóm chứa $X$ và nhóm chứa $Y$ lại thành một nhóm duy nhất.

Thay vì lưu trữ phức tạp, DSU biểu diễn mỗi nhóm như một Cây (Tree) lộn ngược. Mỗi phần tử chỉ cần nhớ duy nhất một thông tin: Ai là cha trực tiếp của mình? (parent[i]).

Đỉnh cao nhất của cây (Root) được gọi là Người đại diện (Representative) của cả nhóm. Đối với Root, cha của nó là chính nó (parent[Root] = Root).
Để biết hai phần tử có chung nhóm hay không, ta bò lên tìm Người đại diện của cả hai. Nếu trùng nhau, chúng đã thông mạng.

2. Hai phép tối ưu thần thánh: Gộp theo Hạng và Nén đường đi

Nếu chúng ta chỉ nối bừa các đỉnh lại với nhau, cây có thể bị thoái hóa thành một đường thẳng dài ngoằng (Linked List), khiến thao tác Find tốn $O(N)$ . Để ép thời gian về mức tiệm cận hằng số, DSU sử dụng 2 kỹ thuật tối ưu:

A. Union by Rank (Gộp theo kích thước/chiều cao)

Khi hợp nhất hai nhóm, ta không nối ngẫu nhiên. Ta duy trì thêm một mảng rank (hoặc size) lưu chiều cao hoặc số lượng phần tử của cái cây.

Quy tắc: Luôn nối gốc của cây nhỏ hơn vào làm con của gốc cây lớn hơn. Điều này đảm bảo chiều cao của cây tăng lên cực kỳ chậm (tối đa là $O(\log N)$ ).

B. Path Compression (Nén đường đi)

Đây là phép tối ưu bá đạo nhất của DSU. Khi thực hiện hàm Find(X) để tìm Người đại diện, thuật toán phải lội ngược dòng từ $X$ lên Root.

Quy tắc: Thay vì chỉ đi lên và trả về kết quả, thuật toán sẽ "bẻ" con trỏ parent của $X$ (và mọi đỉnh trên đường đi) trỏ thẳng trực tiếp vào Root.
Nhờ vậy, ở lần Find tiếp theo, $X$ sẽ nhảy đến Root chỉ trong đúng 1 bước!

Kết hợp cả hai kỹ thuật này, độ phức tạp của DSU giảm xuống $O(\alpha(N))$ — trong đó $\alpha(N)$ là hàm ngược Ackermann. Với $N$ lớn bằng số nguyên tử trong vũ trụ, $\alpha(N)$ cũng không vượt quá $4$ . Nghĩa là DSU chạy với tốc độ $O(1)$ tuyệt đối.

3. Thuật toán Kruskal: Tìm Cây Khung Nhỏ Nhất (MST)

Một trong những ứng dụng vĩ đại nhất của DSU là Thuật toán Kruskal.

Giả sử hệ thống AFC của Metro Line 1 có 14 nhà ga. Bạn cần rải dây cáp quang kết nối tất cả các ga này lại với nhau sao cho tổng chiều dài cáp là ngắn nhất, nhưng mọi ga đều phải được thông mạng. Đồ thị này được gọi là Minimum Spanning Tree (MST).

Thuật toán Kruskal sử dụng DSU để giải bài toán này một cách vô cùng thanh lịch:

Lấy tất cả các cạnh (đoạn cáp) của đồ thị và sắp xếp chúng tăng dần theo chiều dài (trọng số).
Khởi tạo DSU, coi mỗi nhà ga ban đầu là một tập hợp rời rạc.
Duyệt qua danh sách cạnh đã sắp xếp (từ ngắn nhất đến dài nhất).
Với mỗi cạnh nối Trạm $U$ và Trạm $V$ :
- Dùng Find để xem $U$ và $V$ đã thông mạng chưa.
- Nếu chưa: Nối chúng lại bằng Union và đưa cạnh này vào MST.
- Nếu đã thông rồi: Bỏ qua cạnh này (vì nếu nối thêm sẽ tạo thành Chu trình - Cycle, gây lãng phí cáp).
Dừng lại khi đã nối đủ $N-1$ cạnh.

5. Triển khai DSU và Kruskal bằng Golang

Dưới đây là mã nguồn chuẩn mực Golang tích hợp cả Path Compression, Union by Rank và Thuật toán Kruskal.

package main

import (
	"fmt"
	"sort"
)

// Cấu trúc Disjoint Set Union (DSU)
type DSU struct {
	parent []int
	rank   []int
}

func NewDSU(n int) *DSU {
	dsu := &DSU{
		parent: make([]int, n),
		rank:   make([]int, n),
	}
	// Ban đầu, mỗi đỉnh tự làm cha của chính nó
	for i := 0; i < n; i++ {
		dsu.parent[i] = i
		dsu.rank[i] = 0
	}
	return dsu
}

// Hàm Find tích hợp Path Compression (Nén đường đi)
func (dsu *DSU) Find(i int) int {
	if dsu.parent[i] == i {
		return i
	}
	// Đệ quy lên trên, đồng thời cập nhật cha trực tiếp thành Root
	dsu.parent[i] = dsu.Find(dsu.parent[i])
	return dsu.parent[i]
}

// Hàm Union tích hợp Union by Rank
func (dsu *DSU) Union(i, j int) bool {
	rootI := dsu.Find(i)
	rootJ := dsu.Find(j)

	if rootI == rootJ {
		return false // Đã chung nhóm, nối thêm sẽ tạo chu trình
	}

	// Gắn cây lùn vào dưới cây cao
	if dsu.rank[rootI] < dsu.rank[rootJ] {
		dsu.parent[rootI] = rootJ
	} else if dsu.rank[rootI] > dsu.rank[rootJ] {
		dsu.parent[rootJ] = rootI
	} else {
		// Bằng nhau thì gắn bừa một bên, và tăng chiều cao bên đó lên 1
		dsu.parent[rootJ] = rootI
		dsu.rank[rootI]++
	}
	return true
}

// Cấu trúc một Cạnh (Edge)
type Edge struct {
	U, V   int
	Weight int
}

// Thuật toán Kruskal tìm Minimum Spanning Tree
func Kruskal(n int, edges []Edge) ([]Edge, int) {
	// 1. Sắp xếp các cạnh tăng dần theo trọng số (O(E log E))
	sort.Slice(edges, func(i, j int) bool {
		return edges[i].Weight < edges[j].Weight
	})

	dsu := NewDSU(n)
	mst := []Edge{}
	totalCost := 0

	// 2. Duyệt qua các cạnh
	for _, edge := range edges {
		// Nếu Union thành công (không tạo chu trình), chọn cạnh này
		if dsu.Union(edge.U, edge.V) {
			mst = append(mst, edge)
			totalCost += edge.Weight

			// Đã đủ N-1 cạnh thì dừng lại
			if len(mst) == n-1 {
				break
			}
		}
	}
	return mst, totalCost
}

func main() {
	// Giả lập 5 nhà ga (0 đến 4)
	n := 5
	edges := []Edge{
		{0, 1, 10}, {0, 2, 6}, {0, 3, 5},
		{1, 3, 15}, {2, 3, 4}, {1, 4, 2}, {3, 4, 8},
	}

	fmt.Println("Đang tính toán mạng cáp quang tối ưu (MST)...")
	mst, totalCost := Kruskal(n, edges)

	fmt.Printf("Tổng chi phí tối thiểu: %d\n", totalCost)
	fmt.Println("Các đoạn cáp cần triển khai:")
	for _, e := range mst {
		fmt.Printf("Trạm %d <---> Trạm %d (Chi phí: %d)\n", e.U, e.V, e.Weight)
	}
}

6. Phân tích Hiệu năng (Big-O) và Ứng dụng Thực tế

Thời gian Khởi tạo DSU: $O(N)$ .
Thời gian Truy vấn Find/Union: $O(\alpha(N)) \approx \mathbf{O(1)}$ .
Thời gian Kruskal: $O(E \log E)$ do bị chi phối bởi bước sắp xếp (Sort) danh sách các cạnh ban đầu. Bước duyệt vòng lặp DSU cực kỳ nhanh $O(E \cdot \alpha(V))$ .
Không gian (Space): $O(N)$ để lưu trữ 2 mảng parent và rank trong DSU.

Ứng dụng cốt lõi:

Thiết kế Mạng lưới Vật lý (Network Topology): Kruskal là thuật toán tiêu chuẩn để quy hoạch các tuyến cáp quang liên tỉnh, các trạm điện cao thế, hoặc hệ thống đường ống nước sao cho tổng chi phí là rẻ nhất mà vẫn bao phủ toàn bộ các nút.
Phát hiện Chu trình (Cycle Detection): DSU được dùng trong các bộ biên dịch (Compilers) hoặc hệ thống Dependency Injection (như Service Container của Laravel hoặc Wire của Golang) để kiểm tra xem có module nào đang phụ thuộc vòng tròn lẫn nhau (Circular Dependency) hay không.
Phân cụm Hình ảnh (Image Segmentation): Phân chia các pixel lân cận có màu sắc giống nhau thành các cụm (Superpixels) trong xử lý ảnh y tế hoặc Machine Learning.

Từ một cấu trúc đồ thị động, nếu chúng ta cần định tuyến đường đi ngắn nhất không chỉ với chi phí rẻ nhất, mà còn phải tính toán qua hàng triệu node trên bản đồ thực tế với sự trợ giúp của "Trí tuệ nhân tạo (Heuristic)", chúng ta sẽ tiến tới thuật toán nền tảng của mọi ứng dụng bản đồ hiện đại.

cấu trúc dữ liệu