Cấu trúc dữ liệu và Giải thuật Bài 51: Disjoint Set (Union-Find) - Nền tảng quản lý tập hợp và phát hiện chu trình siêu tốc.

Trong thuật toán Kruskal tìm Cây khung nhỏ nhất (Bài 50), bài toán cốt lõi đặt ra là: Làm thế nào để hệ thống kiểm tra ngay lập tức xem hai Đỉnh bất kỳ có đang nằm chung một mạng lưới (cùng một tập hợp) hay chưa?

Nếu dùng DFS hoặc BFS để quét toàn bộ đồ thị kiểm tra liên thông mỗi khi xét một Cạnh mới, chi phí thời gian sẽ tăng vọt, làm tê liệt toàn bộ thuật toán. Để giải quyết bài toán quản lý các tập hợp rời rạc với tốc độ nhanh đến mức phi lý, ngành Khoa học máy tính đã phát minh ra một cấu trúc dữ liệu tinh vi mang tên Disjoint Set (hay Union-Find).

1. Bản chất của Disjoint Set

Disjoint Set quản lý một tập hợp gồm nhiều phần tử được chia thành các nhóm rời rạc (Disjoint Sets). Cấu trúc này chỉ cung cấp 2 thao tác API tối thượng:

Find(x): Đi tìm "Đại diện" (Root/Leader) của nhóm chứa phần tử x. Nếu hai phần tử có cùng một Đại diện, chúng chắc chắn thuộc về cùng một tập hợp (chung một mạng lưới).
Union(x, y): Hợp nhất nhóm chứa phần tử x và nhóm chứa phần tử y lại làm một (nếu chúng ở hai nhóm khác nhau).

Về mặt bộ nhớ, mỗi phần tử được biểu diễn như một Node trỏ ngược về "Cha" của nó (parent[x]). Những Node đứng đầu mỗi nhóm (Root) sẽ có con trỏ trỏ ngược về chính nó, đóng vai trò là Đại diện của cả nhóm.

2. Gót chân Achilles và Hai phép tối ưu vĩ đại

Nếu cài đặt cấu trúc Disjoint Set một cách ngây thơ, khi các phép Union diễn ra liên tục, cây phân cấp sẽ mọc dài thườn thượt và suy biến thành một Danh sách liên kết. Thao tác Find lúc đó sẽ mất thời gian $O(n)$ do phải lội ngược dòng qua hàng ngàn cấp bậc.

Để bóp chết độ trễ này, các nhà khoa học đã tích hợp hai phép tối ưu toán học làm thay đổi hoàn toàn hiệu năng:

A. Path Compression (Nén đường đi trong hàm Find)

Mỗi khi bạn gọi Find(x) để tìm Đại diện, trên đường lội ngược dòng lên Root, hãy tranh thủ cập nhật lại con trỏ parent của mọi Node trên đường đi trỏ thẳng trực tiếp lên Root.

Lần sau, khi có ai đó gọi Find(x), nó sẽ tìm thấy Root ngay lập tức chỉ trong 1 bước nhảy đơn độc ( $O(1)$ ). Cái cây từ cấu trúc dài ngoằng sẽ tự động "bẹp dí" lại thành một cấu trúc phẳng lì.

B. Union by Rank / Size (Hợp nhất theo thứ hạng)

Khi gộp hai nhóm lại với nhau, thay vì nối bừa, ta luôn lấy cái cây có chiều cao thấp hơn (rank nhỏ hơn) gắn vào dưới gốc của cái cây cao hơn. Nhờ vậy, chiều cao tối đa của cây không bao giờ bị phình to vô cớ.

Khi kết hợp cả Path Compression và Union by Rank, thời gian thực thi trung bình cho mọi thao tác giảm xuống còn $\alpha(n)$ (với $\alpha$ là hàm nghịch đảo Ackermann - một hằng số toán học thực tế nhỏ hơn 5 với mọi dữ liệu trong vũ trụ). Nó nhanh đến mức được xem là $O(1)$ tuyệt đối.

3. Triển khai Disjoint Set chuẩn mực bằng Golang

package main

type DisjointSet struct {
    parent []int
    rank   []int // Dùng để tối ưu Union by Rank
}

// Khởi tạo Disjoint Set với n phần tử (từ 0 đến n-1)
func NewDisjointSet(n int) *DisjointSet {
    parent := make([]int, n)
    rank := make([]int, n)
    for i := 0; i < n; i++ {
        parent[i] = i // Ban đầu, mỗi phần tử là cha của chính nó (Đại diện chính mình)
        rank[i] = 0   // Chiều cao ban đầu bằng 0
    }
    return &DisjointSet{parent: parent, rank: rank}
}

// Find với cơ chế Path Compression
func (ds *DisjointSet) Find(i int) int {
    // Nếu i không phải là gốc, đệ quy tìm gốc và nén đường đi
    if ds.parent[i] != i {
        ds.parent[i] = ds.Find(ds.parent[i]) // Path Compression
    }
    return ds.parent[i]
}

// Union với cơ chế Union by Rank
func (ds *DisjointSet) Union(i, j int) bool {
    rootI := ds.Find(i)
    rootJ := ds.Find(j)

    // Nếu chung một gốc nghĩa là chúng đã thuộc cùng một nhóm -> Đã có chu trình!
    if rootI == rootJ {
        return false 
    }

    // Gắn cây thấp hơn vào dưới gốc của cây cao hơn
    if ds.rank[rootI] < ds.rank[rootJ] {
        ds.parent[rootI] = rootJ
    } else if ds.rank[rootI] > ds.rank[rootJ] {
        ds.parent[rootJ] = rootI
    } else {
        ds.parent[rootJ] = rootI
        ds.rank[rootI]++ // Tăng chiều cao nếu 2 cây cao bằng nhau
    }
    return true // Hợp nhất thành công
}

4. Ứng dụng đột phá trong Hệ thống Thực tế

Disjoint Set không chỉ dùng cho Kruskal. Tư duy quản lý nhóm rời rạc này xuất hiện ở mọi nơi cần xử lý quan hệ liên thông tốc độ cao:

Phát hiện Chu trình trong Đồ thị (Cycle Detection): Như trong Kruskal, khi duyệt qua các cạnh, nếu gọi Find(u) == Find(v), hệ thống lập tức kết luận cạnh đó tạo ra chu trình khép kín và loại bỏ nó ngay lập tức chỉ trong $O(1)$ .
Quản lý Mạng lưới Bạn bè (Social Network Components): Khi Facebook muốn tính toán xem có bao nhiêu "Cụm cộng đồng" độc lập trên toàn bộ nền tảng, các mối quan hệ kết bạn được đưa qua hàm Union. Số lượng nhóm độc lập còn lại chính là số lượng tập hợp rời rạc trong Disjoint Set.
Xử lý ảnh (Image Processing - Connected Components): Trong thị giác máy tính, thuật toán phân đoạn ảnh dùng Disjoint Set để quét qua các điểm ảnh (pixels) và gom các điểm có cùng màu sắc sát cạnh nhau thành các vật thể độc lập.

Khép lại chương về Đồ thị, chúng ta đã đi từ những cấu trúc tuyến tính đơn giản cho đến những mạng lưới phức tạp và các công cụ tối ưu siêu tốc. Tuy nhiên, thế giới dữ liệu văn bản (Strings) lại đòi hỏi một tư duy cấu trúc hoàn toàn khác biệt, nơi các ký tự lồng ghép vào nhau như những cành cây cấu thành từ điển.

cấu trúc dữ liệu