TAILIEUCHUNG - HỌ CÁC TẬP KHÔNG CẮT NHAU
Trong chương này chúng ta sẽ nghiên cứu KDLTT họ các tập không cắt nhau (the disjoint set ADT). Chúng ta có một họ các tập con không cắt nhau của một tập đã cho. | Để thấy được thuật toán trên làm việc như thế nào, giả sử tới một giai đoạn nào đó chúng ta có trạng thái của các phòng như trong hình . Ở tình huống này, chúng ta có họ các tập các phòng liên thông với nhau như sau: {0, 1}, {2, 3, 4, 5, 8, 9, 10, 15, 16, 17}, {6}, {7, 12, 13, 18, 24}, {11}, {14, 19, 20, 25, 26}, {21, 27}, {22, 23, 28, 29}. Giả sử đại biểu của một tập con là phòng có số hiệu nhỏ nhất. Bây giờ chúng ta chọn ngẫu nhiên một bức chưa đặt cửa, chẳng hạn đó là bức tường ngăn cách phòng 9 và phòng 15. Chúng ta thấy rằng phòng 9 và phòng 15 đã liên thông với nhau, bởi vì Find(9) = Find(12) = 2, tức là chúng ở trong cùng một tập, và do đó ta để nguyên bức tường này. Chọn ngẫu nhiên một bức tường khác, chẳng hạn bức tường ngăn cách phòng 18 và phòng 19. Phép tìm Find(18) cho ta đại biểu của tập con chứa 18 là 7, phép tìm Find(19) cho ta đại biểu của tập con chứa 19 là 14, như vậy 18 và 19 thuộc các tập con khác nhau, và điều này có nghĩa là chúng không liên thông với nhau. Do đó ta cần đục cửa ở bức tường ngăn cách phòng 18 và 19. Sử dụng phép hợp để hợp nhất tập con chứa 18 và tập con chứa 19 thành một tập con.
đang nạp các trang xem trước
