27.10.2004 1
Các C u Trúc D Li u cho các T p R i Nhauấ ữ ệ ậ ờ
27.10.2004 Ch ng 7: C¸ác c u trúc d li u ươ ấ ữ ệ
cho các t p r i nhauậ ờ 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 ạ ậ ộ ủ ậ ộ 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”.ậ ờ
27.10.2004 Ch ng 7: C¸ác c u trúc d li u ươ ấ ữ ệ
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 MốAKE-SET
– m, s t ng c ng các thao tác Mố ổ ộ AKE-SET, UNION, và FIND-SET.
ªNh n xétậ:
–Sau n 1 l n g i Uầ ọ NION 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 ươ ấ ữ ệ
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 Củ ụ ONNECTED-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 ươ ấ ữ ệ
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 Sủ ụ AME-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