Bài giảng Phân tích thiết kế giải thuật - Chương 7: Các cấu trúc dữ liệu cho các tập rời nhau

Bài giảng Chương 7: Các cấu trúc dữ liệu cho các tập rời nhau trình bày nội dung chính về các thao tác lên cấu trúc dữ liệu các tập rời nhau, ứng dụng của 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. Mời các bạn tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Phân tích thiết kế giải thuật - Chương 7: Các cấu trúc dữ liệu cho các tập rời nhau Các Cấu Trúc Dữ Liệu cho các Tập Rời Nhau 27.10.2004 1 Các thao tác lên cấu trúc dữ liệu các tập rời nhau ª Cấu trúc dữ liệu các tập rời nhau được định nghĩa bởi – Một tập S của các tập động rời nhau, S = {S1 , S2 ,..., Sk} ° Mỗi tập Si được tượng trưng bởi một phần tử đại diện là một  phần tử nào đó của nó. – Các thao tác °  MAKE­SET(x): tạo một tập mới chỉ gồm x. Vì các tập là rời  nhau nên x không được đang nằm trong một tập khác. °  UNION(x, y): tạo tập hội của các tập động S  và S  lần lượt  x y chứa x và y, với điều kiện là Sx và Sy là rời nhau.  °  FIND­SET(x): trả về một con trỏ chỉ đến phần tử đại diện của  tập chứa x. ª Để cho gọn, sẽ dùng “các tập rời nhau” để gọi “cấu trúc dữ liệu các  tập rời nhau”. 27.10.2004 Chương 7: C¸ác cấu trúc dữ liệu  2 cho các tập rời nhau Các thao tác lên các tập rời nhau (tiếp) ª Phân tích thời gian chạy của các thao tác sẽ dựa trên hai tham số sau –  n, số các thao tác MAKE­SET –  m, số tổng cộng các thao tác MAKE­SET, UNION, và FIND­SET. ª Nhận xét: – Sau n   1 lần gọi UNION lên các tập rời nhau thì còn lại đúng một  tập. – m   n. 27.10.2004 Chương 7: C¸ác cấu trúc dữ liệu  3 cho các tập rời nhau Một ứng dụng của các tập rời nhau ª Xác định các thành phần liên thông của một đồ thị vô hướng – Thủ tục CONNECTED­COMPONENTS xác định các thành phần liên  thông của một đồ thị vô hướng.   V[G] là tập các đỉnh của đồ thị G, E[G] là tập các cạnh của G. CONNECTED­COMPONENTS(G) 1    for mỗi đỉnh v   V[G] 2           do MAKE­SET(v) 3    for mỗi cạnh (u, v)   E[G] 4           do if FIND­SET(u)   FIND­SET(v)  5                    then UNION(u, v) 27.10.2004 Chương 7: C¸ác cấu trúc dữ liệu  4 cho các tập rời nhau Một ứng dụng của các tập rời nhau (tiếp) – Thủ tục SAME­COMPONENT xác định hai đỉnh có cùng một thành  phần liên thông hay không. SAME­COMPONENT(u, v) 1    if FIND­SET(u) = FIND­SET(v) 2         then return TRUE 3         else return FALSE 27.10.2004 Chương 7: C¸ác cấu trúc dữ liệu  5 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 Chương 7: C¸ác cấu trúc dữ liệu  6 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 Chương 7: C¸ác cấu trúc dữ liệu  7 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 Chương 7: C¸ác cấu trúc dữ liệu  8 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 MAKE­SET(x): tạo một danh sách liên kết chỉ gồm đối  tượng x. – Hiện thực FIND­SET(x): trả về con trỏ đến đại diện của tập chứa  x. – Hiện thực UNION(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 Chương 7: C¸ác cấu trúc dữ liệu  9 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 Chương 7: C¸ác cấu trúc dữ liệu  10 cho các tập rời nhau Thao tác UNION không dùng heuristic ª Ví dụ một chuỗi gồm 2n   1 thao tác lên n đối tượng mà cần  (n2)  thời gian. Thao tác Số các đối tượng được cập nhật MAKE­SET(x1 ) 1 MAKE­SET(x2 ) 1 . . n . MAKE­SET(xn ) 1 UNION(x1 , x2 ) 1 UNION(x2 , x3 ) 2 UNION(x3 , x4 ) 3 . (n2) . . UNION(xn   1 , xn ) n   1 27.10.2004 Chương 7: C¸ác cấu trúc dữ liệu  11 cho các tập rời nhau Heuristic để tăng tốc của UNION ª Nhận xét: Khi hợp hai danh sách trong UNION, 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 ...