intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

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

Chia sẻ: Đinh Trường Gấu | Ngày: | Loại File: PPT | Số trang:26

Thêm vào BST
Báo xấu
68
lượt xem 2
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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

  1. Các Cấu Trúc Dữ Liệu cho các Tập Rời Nhau 27.10.2004 1
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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ê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 Chương 7: C¸ác cấu trúc dữ liệu  12 cho các tập rời nhau
  13. Heuristic hợp theo trọng số ª Ví dụ chiều dài = 4 chiều dài = 3 c h e b f g d 27.10.2004 Chương 7: C¸ác cấu trúc dữ liệu  13 cho các tập rời nhau
  14. 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 MAKE­SET, UNION, và FIND­SET, trong đó có n thao tác là  MAKE­SET, tốn O(m   n lg n) thời gian. Chứng minh – Mỗi MAKE­SET chạy trong thời gian O(1) – Mỗi FIND­SET chạy trong thời gian O(1) – Xác định thời gian chạy của các thao tác UNION: ° Thời gian chạy của các thao tác UNION 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 Chương 7: C¸ác cấu trúc dữ liệu  14 cho các tập rời nhau
  15. 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 2k phần  tử.   Vì tập có nhiều lắm là n phần tử nên 2k   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) . Chương 7: C¸ác c 27.10.2004 ấu trúc dữ liệu  cho các tập rời nhau 15
  16. 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 Chương 7: C¸ác cấu trúc dữ liệu  16 cho các tập rời nhau
  17. 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 Chương 7: C¸ác cấu trúc dữ liệu  17 cho các tập rời nhau
  18. 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 MAKE­SET: tạo một cây chỉ có một nút. – Hiện thực FIND­SET 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 FIND­SET tạo thành đường dẩn  (find path). – Hiện thực UNION: 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 Chương 7: C¸ác cấu trúc dữ liệu  18 cho các tập rời nhau
  19. 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 UNION(e, g). UNION 27.10.2004 Chương 7: C¸ác cấu trúc dữ liệu  19 cho các tập rời nhau
  20. 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 UNION: ° 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 Chương 7: C¸ác cấu trúc dữ liệu  20 cho các tập rời nhau
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2