Bài giảng Giải thuật - Chương 7: Các cấu trúc dữ liệu cho các tập rời nhau

âng. 
S AME -C OMPONENT ( u , v ) 
1 if F IND -S ET ( u ) = F IND -S ET ( v ) 
2 then return TRUE 
3 else return FALSE 
27.10.2004 
5 
Chương 7: C¸ ác cấu trúc dữ liệu cho các tập rời nhau 
Thao tác lên các tập rời nhau 
Ví dụ: một đồ thị với 4 thành phần liên thông 
27.10.2004 
6 
Chương 7: C¸ ác cấu trúc dữ liệu cho các tập rời nhau 
Biểu diễn các tập rời nhau dùng danh sách liên kết 
Biểu diễn các tập rời nhau dùng danh sách liên kết (linked-list representation of disjoint sets): 
Biểu diễn mổi tập bằng một danh sách liên kết . Trong mỗi danh sách liên kết 
Đối tượng đứng đầu được dùng làm phần tử đại diện của tập. 
Mổi đối tượng trong danh sách liên kết chứa 
phần tử của tập 
con trỏ chỉ đến đối tượng chứa phần tử kế tiếp 
con trỏ chỉ đến phần tử đại diện của tập. 
Con trỏ head chỉ đến đại diện của tập. Con trỏ tail chỉ đến phần tử cuối trong danh sách. 
27.10.2004 
7 
Chương 7: C¸ ác cấu trúc dữ liệu cho các tập rời nhau 
Biểu diễn tập bằng danh sách liên kết 
Ví dụ 
head 
tail 
head 
tail 
27.10.2004 
8 
Chương 7: C¸ ác cấu trúc dữ liệu cho các tập rời nhau 
Biểu diễn tập bằng danh sách liên kết (tiếp) 
Hiện thực các thao tác 
Hiện thực M AKE -S ET ( x ): tạo một danh sách liên kết chỉ gồm đối tượng x . 
Hiện thực F IND -S ET ( x ): trả về con trỏ đến đại diện của tập chứa x . 
Hiện thực U NION ( x , y ): 
gắn danh sách của x vào đuôi của danh sách của y 
cập nhật các con trỏ của các đối tượng trong danh sách cũ của x để chúng chỉ đến đại diện của tập, tức là đầu của danh sách cũ của y . 
27.10.2004 
9 
Chương 7: C¸ ác cấu trúc dữ liệu cho các tập rời nhau 
Biểu diễn tập bằng danh sách liên kết (tiếp) 
Ví dụ 
27.10.2004 
10 
Chương 7: C¸ ác cấu trúc dữ liệu cho các tập rời nhau 
Thao tác U NION không dùng heuristic 
Ví dụ một chuỗi gồm 2 n - 1 thao tác lên n đối tượng mà cần ( n 2 ) thời gian. 
Thao tác 	 Số các đối tượng được cập nhật 
M AKE -S ET ( x 1 )	1 
M AKE -S ET ( x 2 )	1 
	. 
	. 
	. 
M AKE -S ET ( x n )	1 
U NION ( x 1 , x 2 )	1 
U NION ( x 2 , x 3 )	2 
U NION ( x 3 , x 4 )	3 
	. 
	. 
	. 
U NION ( x n - 1 , x n )	 n - 1 
( n 2 ) 
n 
27.10.2004 
11 
Chương 7: C¸ ác cấu trúc dữ liệu cho các tập rời nhau 
Heuristic để tăng tốc của U NION 
Nhận xét : Khi hợp hai danh sách trong U NION , mọi con trỏ (chỉ đến đại diện mới) của các phần tử trong danh sách được gắn vào đuôi của danh sách kia phải được cập nhật. 
Giả sử mỗi danh sách có chứa thêm chiều dài của nó. 
Heuristic hợp theo trọng số (weighted-union heuristic): khi hợp hai danh sách 
gắn danh sách ngắn hơn vào đuôi của danh sách dài hơn (nếu các danh sách dài như nhau thì có thể gắn tùy ý). 
27.10.2004 
12 
Chương 7: C¸ ác cấu trúc dữ liệu cho các tập rời nhau 
Heuristic hợp theo trọng số 
Ví dụ 
c 
h 
e 
b 
f 
g 
d 
chiều dài = 4 
chiều dài = 3 
27.10.2004 
13 
Chương 7: C¸ ác cấu trúc dữ liệu cho các tập rời nhau 
Biểu diễn tập bằng danh sách liên kết: thời gian chạy 
Định lý (Theorem 22.1) 
	Bằng cách dùng biểu diễn danh sách liên kết cho các tập rời nhau và heuristic hợp theo trọng số (weighted-union heuristic), một dãy gồm có m thao tác M AKE -S ET , U NION , và F IND -S ET , trong đó có n thao tác là M AKE -S ET , tốn O ( m + n lg n ) thời gian. 
	 Chứng minh 
Mỗi M AKE -S ET chạy trong thời gian O (1) 
Mỗi F IND -S ET chạy trong thời gian O (1) 
Xác định thời gian chạy của các thao tác U NION : 
Thời gian chạy của các thao tác U NION là thời gian tổng cộng lấy trên mọi phần tử của mọi lần cập nhật con trỏ chỉ đến phần tử đại diện của tập chứa phần tử đó. 
27.10.2004 
14 
Chương 7: C¸ ác cấu trúc dữ liệu cho các tập rời nhau 
Biểu diễn tập bằng danh sách liên kết: thời gian chạy 
	 Chứng minh (tiếp theo) 
Xét đối tượng x bất kỳ trong một tập bất kỳ của các tập rời nhau . Mỗi lần con trỏ chỉ đến phần tử đại diện của tập chứa x được cập nhật, thì x phải đã nằm trong tập nhỏ hơn 
 
Lần 1 cập nhật con trỏ của x : tập kết quả phải có ít nhất 2 phần tử 
Lần 2 cập nhật con trỏ của x : tập kết quả phải có ít nhất 4 phần tử 
Lần k cập nhật con trỏ của x : tập kết quả phải có ít nhất 2 k phần tử. 
Vì tập có nhiều lắm là n phần tử nên 2 k  n . Vậy số lần cập nhật con trỏ của x nhiều lắm là k  lg n . 
Vì x là phần tử bất kỳ nên thời gian tổng cộng để cập nhật các con trỏ của mọi phần tử là O ( n lg n ). 
Thời gian chạy tổng cộng của dãy m thao tác là: O ( m ) + O ( n lg n ) = O ( m + n lg n ) . 
27.10.2004 
15 
Chương 7: C¸ ác cấu trúc dữ liệu cho các tập rời nhau 
Biểu diễn các tập rời nhau bằng rừng 
Biểu diễn các tập rời nhau bằng rừng ( disjoint-set forest ) 
Biểu diễn mỗi tập bằng một cây có gốc : 
Mỗi nút của cây chứa một phần tử của tập 
ngoài ra 
Mỗi nút chứa một con trỏ chỉ đến cha của nó 
Gốc của mỗi cây chứa đại diện của tập và là cha của chính nó. 
27.10.2004 
16 
Chương 7: C¸ ác cấu trúc dữ liệu cho các tập rời nhau 
Biểu diễn các tập rời nhau bằng rừng (tiếp) 
Ví dụ 
Hai cây sau biểu diễn các tập { b , c , e , h } và { d , f , g }. 
c và f lần lượt là phần tử đại diện của các tập { b , c , e , h } và { d , f , g }. 
27.10.2004 
17 
Chương 7: C¸ ác cấu trúc dữ liệu cho các tập rời nhau 
Biểu diễn các tập rời nhau bằng rừng: các thao tác 
Các thao tác lên các tập rời nhau khi biểu diễn bằng rừng 
Hiện thực M AKE -S ET : tạo một cây chỉ có một nút. 
Hiện thực F IND -S ET bằng cách đuổi theo các con trỏ chỉ đến nút cha cho đến khi tìm được nút gốc của cây. 
Các nút được ghé qua khi gọi F IND -S ET tạo thành đường dẩn ( find path ). 
Hiện thực U NION : làm cho con trỏ của gốc cây này chỉ đến gốc của cây kia. 
27.10.2004 
18 
Chương 7: C¸ ác cấu trúc dữ liệu cho các tập rời nhau 
Biểu diễn các tập rời nhau bằng rừng 
Ví dụ 
Hình (b) là kết quả của U NION ( e , g ). 
U NION 
27.10.2004 
19 
Chương 7: C¸ ác cấu trúc dữ liệu cho các tập rời nhau 
Biểu diễn tập bằng cây 
Dùng hai heuristics để giảm thời gian chạy của các dãy các thao tác lên các tập rời nhau khi hiện thực bằng rừng: 
Heuristic hợp theo thứ hạng ( union by rank ) khi thực thi U NION : 
duy trì cho mỗi nút một rank . Rank là cận trên cho độ cao (*) của nút. Mọi nút được khởi tạo với rank = 0. 
khi hợp theo thứ hạng hai cây, nút gốc có rank nhỏ hơn được làm thành con của nút có rank lớn hơn. 
Heuristic nén đường dẩn ( path compression ). 
(*) Độ cao của một nút trong một cây là số các cạnh nằm trên đường đi đơn dài nhất từ nút đến một nút lá. 
27.10.2004 
20 
Chương 7: C¸ ác cấu trúc dữ liệu cho các tập rời nhau 
Heuristic hợp theo thứ hạng 
Ví dụ: (số bên cạnh mỗi đối tượng là rank của nó.) 
c 
d 
c 
f 
e 
1 
0 
b 
a 
a 
c 
1 
0 
b 
0 
0 
U NION 
U NION 
e 
1 
0 
c 
f 
1 
0 
d 
2 
0 
0 
1 
27.10.2004 
21 
Chương 7: C¸ ác cấu trúc dữ liệu cho các tập rời nhau 
Heuristic nén đường dẫn 
Heuristic nén đường dẩn ( path compression ). Chạy qua hai giai đoạn khi thực thi F IND -S ET : 
giai đoạn chạy lên để tìm gốc của cây, 
giai đoạn chạy xuống để cập nhật các nút trên đường dẩn để chúng chỉ trực tiếp đến gốc. 
27.10.2004 
22 
Chương 7: C¸ ác cấu trúc dữ liệu cho các tập rời nhau 
Heuristic nén đường dẩn (tiếp) 
Minh họa heuristic nén đường dẫn do thao tác F IND -S ET 
Các hình tam giác tượng trưng các cây con có gốc tại các nút trong hình (a). Mỗi nút có con trỏ chỉ đến nút cha của nó. 
Hình (b): sau khi thực thi F IND -S ET ( a ) 
27.10.2004 
23 
Chương 7: C¸ ác cấu trúc dữ liệu cho các tập rời nhau 
Các heuristic hợp theo thứ hạng và nén đường dẩn 
Các thủ tục hiện thực các heuristics hợp theo thứ hạng và nén đường dẫn: M AKE -S ET , U NION , và F IND -S ET 
Cha của nút x là p [ x ]. 
M AKE -S ET ( x ) 
1 p [ x ]  x 
2 rank [ x ]  0 
U NION ( x , y ) 
1 L INK (F IND -S ET ( x ), F IND -S ET ( y )) 
L INK ( x , y ) 
1 if rank [ x ] > rank [ y ] 
2 then p [ y ]  x 
3 else p [ x ]  y 
4 if rank [ x ] = rank [ y ] 
5 then rank [ y ]  rank [ y ] + 1 
27.10.2004 
24 
Chương 7: C¸ ác cấu trúc dữ liệu cho các tập rời nhau 
Các heuristics hợp theo thứ hạng và nén đường dẩn (tiếp) 
F IND -S ET ( x ) 
1 if x  p [ x ] 
2 then p [ x ]  F IND -S ET ( p [ x ]) 
3 return p [ x ] 
27.10.2004 
25 
Chương 7: C¸ ác cấu trúc dữ liệu cho các tập rời nhau 
Aûnh hưởng của các heuristics lên thời gian chạy 
Thời gian chạy của một dãy các thao tác gồm m M AKE -S ET , U NION , và F IND -S ET , trong đó có n thao tác M AKE -S ET: 
Nếu chỉ dùng heuristic hợp theo thứ hạng 
 O ( m lg n ) 
Nếu chỉ dùng heuristic nén đường dẩn, với f là số thao tác F IND -S ET 
( f log (1 + f / n ) n )	nếu f  n 
( n + f lg n )	nếu f  n 
Nếu dùng cả hai heuristics hợp theo thứ hạng và nén đường dẩn 
O ( m a ( m , n )) 
 a ( m , n ) là hàm đảo của hàm Ackermann 
trong mọi ứng dụng thực tế, a ( m , n )  4 . 
(Không chứng minh các chận đã liệt kê ở trên.) 
27.10.2004 
26 
Chương 7: C¸ ác cấu trúc dữ liệu cho các tập rời nhau