DISJOINT-SET (CẤU TRÚC DỮ LIỆU)

Go down

DISJOINT-SET (CẤU TRÚC DỮ LIỆU)

Bài gửi  ductam on Sun Sep 05, 2010 11:21 am

Một cấu trúc dữ liệu rất hữu dụng trong lý thuyết đồ thị ,cũng như các bài tập trong OLP và các "constest online", đó là DISJOINT-SET.
Link tham khảo thêm: http://en.wikipedia.org/wiki/Disjoint_sets
Các bạn có thể tham khảo link trên và dùng Google search thêm, Mình chỉ nói đơn giản như sau :
Các phép toán trong DISJOINT-SET:
- Create(x) - Khỏi tạo cây có gốc là x
- Find(x) - Tìm gốc của nút x
- Union(x,y) - Hợp cây chứa nút x và cây chứa nút y.
Đề cài đặt có hiệu quả, chúng ta có hai heusrictics: Union by rank và Path Compress.
Sau đây mình chỉ nói về Union by rank.
Để tránh suy biến thì ta có quy tắc hợp hai cây như sau, cây nào mà nút gốc có rank lớn hơn thì sẽ là nút gốc của cây kia.

Các phép toán được cài đặt chi tiết như sau:
Code:

void Create(int x)
{
 rank[x]=0;
 P[x]=x;   
}
int Find(int x)
{
 if(x==P[x]) return x;
 return Find(P[x]); 
}
void Union(int x,int y)
{
 int px=Find(x);   
 int py=Find(y);
 if(rank[px]>rank[py]) P[py]=px;
 else P[px]=py;
 if(rank[px]==rank[py]) rank[py]++;
}
Các bạn thấy cài đặt cực kì đơn giản nhưng có tầm ứng dụng rất rộng rãi và mạnh mẽ trong nhiều bài toán.
Bài toán vận dụng:
Trong một hội nghị cấp cao, Người A quen với B, B quen với C thì A cũng sẽ quen với C. Như vậy sau hội nghị người i, có quen người j không?
avatar
ductam
Thành viên cấp 2
Thành viên cấp 2

Tổng số bài gửi : 11
Ngày tham gia : 18/07/2010

Xem lý lịch thành viên

Về Đầu Trang Go down

Về Đầu Trang


 
Permissions in this forum:
Bạn không có quyền trả lời bài viết