1. Tập dữ liệu rời nhau
Tập dữ liệu rời nhau (thường được gọi là Disjoint Set Union - DSU hoặc Union-Find) là một cấu trúc dữ liệu (CTDL) lưu trữ một tập hợp các phần tử được phân hoạch thành nhiều tập con rời nhau (không giao nhau).
CTDL này cho phép thực hiện 2 thao tác rất hiệu quả là xác định xem 2 phần tử có thuộc cùng một tập hợp hay không và gộp 2 tập hợp lại với nhau.
Để dễ hiểu, chúng ta sẽ xét một ví dụ cụ thể: Xây dựng mạng lưới bạn bè
1.1 Bối cảnh bài toán: “Xây dựng mạng lưới bạn bè”
Giả sử mạng xã hội facebook (FB) bắt đầu với N người dùng hoàn toàn xa lạ (chưa ai quen ai). Khi một người muốn kết bạn với một người khác, server của FB liên tục phải xử lý 2 việc sau:
1. Kiểm tra kết nối (find): Xem hai người A và B có đang cùng một mạng lưới bạn bè với nhau không?
2. Kết bạn (Union): Khi A và B trực tiếp kết bạn với nhau, hai mạng lưới bạn bè của họ sẽ nhập lại thành một mạng lưới lớn hơn
1.2 Ánh xạ các thao tác của DSU vào mạng xã hội
1.3. Ví dụ minh họa từng bước
Giả sử mạng xã hội FB có 5 người dùng: các người dùng có ID (mã định danh) từ 1 đến 5. Ban đầu, chưa ai kết bạn với ai:
Sử dụng mảng có tên là parent để lưu các “đại diện mạng lưới”, mỗi người tự làm đại diện cho mạng lưới của họ:
parent = [1, 2, 3, 4, 5]
Bước 1: Người dùng 1 kết bạn với người dùng 2
Union(1, 2)
- Hệ thống tìm đại diện của 1 là 1, đại diện của 2 là 2. Do hai người thuộc hai nhóm khác nhau, nên sẽ thực hiện gộp lại
- Cập nhật: Cho người 2 trỏ về và nhận người 1 làm đại diện chung
Bước 2: Người dùng 3 kết bạn với người dùng 4
Union(3, 4)
- Hệ thống tìm đại diện của 3 là 3, đại diện của 4 là 4. Do hai người thuộc hai nhóm khác nhau, nên sẽ thực hiện gộp lại
- Cập nhật: Cho người 4 trỏ về và nhận người 3 làm đại diện chung
Bước 3: Người dùng 2 kết bạn với người dùng 3
Union(2, 3)
- Hệ thống tìm đại diện của 2 là người 1 và đại diện của 3 là người 3. Vì hai đại diện khác nhau (1 và 3), nên hệ thống sẽ tiến hành sáp nhập hai mạng lưới này lại thành một. Mạng lưới của 3 nhận 1 làm đại diện chung
- Kết quả: Lúc này nhóm {1, 2} và nhóm {3, 4} đã gộp lại thành mạng lưới lớn gồm 4 người {1, 2, 3, 4}
Bước 4: Kiểm tra “là bạn” (Find)
Khi hệ thống cần kiểm tra xem người dùng 4 có thuộc cùng mạng lưới bạn bè với người dùng 1 hay không, thực hiện các bước sau:
- Find(4) đi ngược lên tìm thấy đại diện là 1
- Find(1) thấy đại diện là 1
- Vì Find(4) == Find(1), nên hệ thống kết luận hai người này cùng thuộc một mạng lưới bạn bè mà không cần phải duyệt qua toàn bộ danh sách bạn bè phức tạp
1.4 Cài đặt trên Python
class FriendNetworkDSU:
def __init__(self, n):
"""
Khởi tạo mạng lưới với n người dùng (ID từ 1 đến n).
Mảng parent lưu đại diện của từng người, ban đầu mỗi người tự làm đại diện cho chính mình.
(Lưu ý: Index 0 không dùng để dễ khớp với ID từ 1 đến n).
"""
self.parent = list(range(n + 1))
def find(self, user_id):
"""
Tìm đại diện (gốc) của mạng lưới chứa user_id.
Đi ngược lên cha của mình cho đến khi gặp người tự làm đại diện.
"""
if self.parent[user_id] == user_id:
return user_id
# Đệ quy tìm đại diện cấp cao hơn
return self.find(self.parent[user_id])
def union(self, user_a, user_b):
"""
Gộp hai mạng lưới bạn bè chứa user_a và user_b lại với nhau.
"""
root_a = self.find(user_a)
root_b = self.find(user_b)
if root_a != root_b:
# Hai người ở hai mạng lưới khác nhau -> gộp lại
# Cho đại diện của mạng lưới b trỏ về và nhận đại diện của mạng lưới a làm gốc chung
self.parent[root_b] = root_a
print(f"-> Kết bạn thành công: Người {user_b} và người {user_a} đã chung một mạng lưới (Gốc chung: {root_a})")
return True
else:
print(f"-> Người {user_a} và người {user_b} đang ở cùng một mạng lưới rồi!")
return False
def are_connected(self, user_a, user_b):
"""
Kiểm tra xem hai người có cùng 1 mạng lưới bạn bè hay không (Find check).
"""
return self.find(user_a) == self.find(user_b)
# ==========================================
# CHẠY THỬ NGHIỆM
# ==========================================
if __name__ == "__main__":
# Giả sử mạng xã hội có 5 người dùng (ID từ 1 đến 5)
n = 5
fb_network = FriendNetworkDSU(n)
print(f"Đại diện ban đầu (parent): {fb_network.parent[1:]}\n")
# Bước 1: Người dùng 1 kết bạn với người dùng 2
print("--- Bước 1: Union(1, 2) ---")
fb_network.union(1, 2)
print(f"Trạng thái parent hiện tại: {fb_network.parent[1:]}\n")
# Bước 2: Người dùng 3 kết bạn với người dùng 4
print("--- Bước 2: Union(3, 4) ---")
fb_network.union(3, 4)
print(f"Trạng thái parent hiện tại: {fb_network.parent[1:]}\n")
# Bước 3: Người dùng 2 kết bạn với người dùng 3
print("--- Bước 3: Union(2, 3) ---")
fb_network.union(2, 3)
print(f"Trạng thái parent hiện tại: {fb_network.parent[1:]}\n")
# Bước 4: Kiểm tra "là bạn" (Find) giữa người 4 và người 1
print("--- Bước 4: Kiểm tra kết nối Find(4) và Find(1) ---")
root_1 = fb_network.find(1)
root_4 = fb_network.find(4)
print(f"Đại diện của người 1 là: {root_1}")
print(f"Đại diện của người 4 là: {root_4}")
if fb_network.are_connected(1, 4):
print("=> Kết luận: Người dùng 4 và người dùng 1 cùng thuộc một mạng lưới bạn bè!")
else:
print("=> Kết luận: Hai người này KHÔNG cùng 1 mạng lưới.")
1.5 Xem và đọc thêm
Sử dụng các từ khóa sau, tìm kiếm trên Google, Youtube, Chatbot để xem và đọc thêm: Tập dữ liệu rời nhau, Cấu trúc dữ liệu DSU.
1.6 Bài tập và câu hỏi
Bài tập
Bài tập 1.1: Tự tay viết lại từng dòng mã trong phần lý thuyết, tìm hiểu ý nghĩa từng dòng mã.
Bài tập 1.2: Dựa trên ví dụ trong phần lý thuyết, thực hiện các yêu cầu sau:
a. Khởi tạo một mạng xã hội gồm 6 người dùng. Khi đó:
parent = [1, 2, 3, 4, 5, 6]
b. Lập trình các lệnh kết bạn để parent có trạng thái là:
parent = [1, 1, 1, 1, 5, 1]
Câu hỏi
Câu 1a: Trong ngữ cảnh bài toán xây dựng mạng lưới bạn bè sử dụng cấu trúc dữ liệu DSU, thao tác Union(user_A, user_B) có ý nghĩa tương đương với hoạt động nào sau đây trên mạng xã hội?
A. Đăng ký tài khoản mới cho một người dùng
B. Tìm người đại diện cho mạng lưới bạn bè của một người dùng
C. Kết bạn trực tiếp, gộp toàn bộ thành viên trong mạng lưới của hai người lại thành một
D. Kiểm tra xem hai người có đang cùng một mạng lưới bạn bè hay không
Câu 1b: Trong đoạn mã cài đặt DSU bằng Python trong tài liệu, mảng parent ban đầu với n người dùng được khởi tạo như thế nào?
A. Tất cả các phần tử đều được gán giá trị bằng 0 để dễ đồng bộ index
B. Mỗi người tự làm đại diện cho chính mình (parent[user_id] == user_id)
C. Tất cả các phần tử đều trỏ chung về một người dùng duy nhất có ID là 1
D. Mảng parent để trống và chỉ thêm phần tử khi có người kết bạn
Câu 1c: Dựa vào ví dụ minh họa từng bước trong tài liệu (với 5 người dùng, ban đầu parent = [1, 2, 3, 4, 5]), sau khi thực hiện lần lượt các lệnh Union(1, 2), Union(3, 4), và Union(2, 3), kết quả cấu trúc các nhóm lúc đó sẽ như thế nào?
A. Tạo thành 3 nhóm rời nhau gồm: nhóm {1, 2}, nhóm {3, 4}, và nhóm {5} đứng riêng lẻ
B. Nhóm {1, 2} và nhóm {3, 4} được sáp nhập lại thành một mạng lưới lớn gồm 4 người {1, 2, 3, 4}, còn người dùng 5 vẫn đứng riêng
C. Tất cả 5 người dùng đều được gộp chung vào một mạng lưới duy nhất có gốc đại diện là 5
D. Cả 5 người dùng đều trở thành các tập hợp độc lập hoàn toàn và không có liên kết nào
Câu 1d: Cho một mạng xã hội gồm 6 người dùng với mảng parent ban đầu là [1, 2, 3, 4, 5, 6]. Sau một chuỗi các thao tác kết bạn, mảng parent (từ index 1 đến 6) cập nhật thành trạng thái: [1, 1, 1, 1, 5, 1]. Dựa vào thuật toán find trong tài liệu, khi hệ thống gọi hàm kiểm tra are_connected(2, 4), kết quả trả về sẽ là gì và vì sao?
A. False, vì người dùng 2 và người dùng 4 có các giá trị cha trực tiếp trong mảng khác nhau
B. True, vì khi thực hiện truy ngược tìm gốc, cả người 2 và người 4 đều có chung một đại diện cấp cao nhất là 1
C. False, vì người dùng 4 thuộc về mạng lưới của người dùng 5, trong khi người dùng 2 thuộc về mạng lưới khác
D. True, vì người dùng 2 và người dùng 4 trỏ trực tiếp vào nhau trong cấu trúc cây