Trong bài toán Minimum Spanning Tree áp dụng thuật toán Kruskal, tại sao việc sử dụng Disjoint Set Union kết hợp Path Compression và Union by Rank lại là tiêu chuẩn bắt buộc khi xử lý mạng lưới viễn thông hoặc hạ tầng Microservices quy mô lớn?

Question

Accepted Answer

Khi xây dựng mạng lưới kết nối tối ưu (ví dụ: kết nối các trung tâm dữ liệu với chi phí cáp quang thấp nhất), Kruskal Algorithm là giải pháp Greedy tối ưu. Tuy nhiên, hiệu năng của thuật toán phụ thuộc hoàn toàn vào tốc độ kiểm tra chu trình và hợp nhất các tập hợp đỉnh.
Bản chất cơ chế hoạt động

Sắp xếp tất cả các cạnh trong đồ thị theo trọng số tăng dần.
Duyệt qua từng cạnh và kiểm tra xem hai đỉnh của cạnh đó có thuộc cùng một thành phần liên thông hay không bằng cấu trúc dữ liệu Disjoint Set Union (DSU).
Nếu không cùng thành phần liên thông, thêm cạnh vào tập hợp Minimum Spanning Tree và hợp nhất hai tập hợp đỉnh lại.

Tối ưu hóa với Path Compression và Union by Rank

Path Compression: Trong hàm tìm kiếm gốc find(i), cập nhật trực tiếp con trỏ của mọi nút trên đường đi trỏ thẳng về gốc, giúp giảm chiều cao của cây.
Union by Rank: Khi hợp nhất hai cây, luôn gắn cây có chiều cao nhỏ hơn vào gốc của cây có chiều cao lớn hơn để giữ cho cây cân bằng.

Ví dụ mã nguồn minh họa bằng JavaScript
class DSU {
    constructor(n) {
        this.parent = Array.from({ length: n }, (_, i) => i);
        this.rank = new Array(n).fill(0);
    }

find(i) {
        if (this.parent[i] === i) {
            return i;
        }
        // Path Compression
        return this.parent[i] = this.find(this.parent[i]);
    }

union(i, j) {
        let rootI = this.find(i);
        let rootJ = this.find(j);

if (rootI !== rootJ) {
            // Union by Rank
            if (this.rank[rootI] < this.rank[rootJ]) {
                this.parent[rootI] = rootJ;
            } else if (this.rank[rootI] > this.rank[rootJ]) {
                this.parent[rootJ] = rootI;
            } else {
                this.parent[rootJ] = rootI;
                this.rank[rootI]++;
            }
            return true;
        }
        return false;
    }
}
Lưu ý kinh nghiệm thực chiến Enterprise

Độ phức tạp thời gian khi áp dụng cả hai tối ưu trên giảm xuống gần như tuyến tính O(alpha(n)) với alpha là hàm nghịch đảo Ackermann, cực kỳ hiệu quả cho hệ thống xử lý đồ thị hàng triệu đỉnh.
Cần cẩn trọng với giới hạn bộ nhớ Stack khi đệ quy hàm find nếu không dùng kỹ thuật lặp (iterative) hoặc Path Compression triệt để.

Trong bài toán Minimum Spanning Tree áp dụng thuật toán Kruskal, tại sao việc sử dụng Disjoint Set Union kết hợp Path Compression và Union by Rank lại là tiêu chuẩn bắt buộc khi xử lý mạng lưới viễn thông hoặc hạ tầng Microservices quy mô lớn?

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi greedy algorithms liên quan cùng chủ đề