Khi triển khai hệ thống phân quyền (Access Control) dựa trên cấu trúc cây (Tree) hoặc đồ thị, tại sao việc sử dụng Disjoint Set Union (DSU) lại hiệu quả hơn so với việc duyệt đồ thị truyền thống để kiểm tra tính liên thông?

Question

Accepted Answer

Bản chất của DSU
Disjoint Set Union (DSU) hay còn gọi là Union-Find là cấu trúc dữ liệu chuyên biệt để quản lý các tập hợp rời nhau. Thay vì duyệt toàn bộ đồ thị mỗi khi cần kiểm tra xem hai đối tượng có cùng quyền truy cập hay không, DSU duy trì các nhóm thông qua hai thao tác chính: Find (tìm đại diện nhóm) và Union (hợp nhất hai nhóm).
Ưu điểm vượt trội

Tốc độ: Với kỹ thuật Path Compression và Union by Rank, độ phức tạp của mỗi thao tác gần như là hằng số O(alpha(N)), trong đó alpha là hàm ngược của Ackermann, cực kỳ nhanh.
Tiết kiệm tài nguyên: Không cần lưu trữ toàn bộ danh sách kề (Adjacency List) của đồ thị, chỉ cần một mảng parent[] để lưu trữ cấu trúc.

Ứng dụng thực chiến
Trong hệ thống Enterprise, DSU cực kỳ hữu ích khi cần kiểm tra nhanh liệu hai User có thuộc cùng một nhóm quyền (Role Group) hoặc cùng một tổ chức (Organization Unit) hay không mà không cần thực hiện các truy vấn đệ quy tốn kém trên cây phân cấp.
Lưu ý
DSU chỉ hiệu quả với các quan hệ mang tính chất bắc cầu và không có hướng. Nếu hệ thống yêu cầu kiểm tra quyền dựa trên thứ bậc (Inheritance), DSU cần được kết hợp với các kỹ thuật khác như Nested Sets hoặc Path Enumeration.

Khi triển khai hệ thống phân quyền (Access Control) dựa trên cấu trúc cây (Tree) hoặc đồ thị, tại sao việc sử dụng Disjoint Set Union (DSU) lại hiệu quả hơn so với việc duyệt đồ thị truyền thống để kiểm tra tính liên thông?

Bản chất của DSU

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 graph theory liên quan cùng chủ đề