tailieunhanh - 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. | Các Cấu Trúc Dữ Liệu cho các Tập Rời Nhau Chương 7: C¸ác cấu trúc dữ liệu cho các tập rời nhau 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 Sx và Sy lần lượt 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”. Chương 7: C¸ác cấu trúc dữ liệu 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. Chương 7: C¸ác cấu trúc dữ liệu 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) Chương 7: C¸ác cấu trúc dữ liệu 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 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 . | Các Cấu Trúc Dữ Liệu cho các Tập Rời Nhau Chương 7: C¸ác cấu trúc dữ liệu cho các tập rời nhau 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 Sx và Sy lần lượt 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”. Chương 7: C¸ác cấu trúc dữ liệu 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