ữ ệ

ấ

ậ

ờ

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 đ nh nghĩa b i

ượ ị ữ ệ  các t p r i nhau ậ ờ ờ ộ ậ ộ ậ S c a các t p đ ng r i nhau, ấ ª C u trúc d  li u ủ – M t t p

ư S = {S1 , S2 ,..., Sk} ộ ạ ầ ử đ i di n ở ng tr ng b i m t ph n t ệ  là m t ộ

ượ ượ c t ủ  nào đó c a nó.

°

ỗ ậ Si đ ° M i t p  ầ ử ph n t – Các thao tác

ậ ờ ạ ỉ ồ x. Vì các t p là r i

°

ớ ằ

ậ ầ ượ t ộ ậ Sx và Sy l n l

°

ờ ộ ậ  MAKE­SET(x): t o m t t p m i ch  g m  ượ 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  ệ ề ớ ch a ứ x và y, v i đi u ki n là

ầ ử ạ ả ề ộ ỏ ỉ ế ệ ủ đ i di n c a

ª Đ  cho g n, s  dùng “các t p r i nhau” đ  g i “c u trúc d  li u các

ộ Sx và Sy là r i nhau.   FIND­SET(x): tr  v  m t con tr  ch  đ n ph n t ứ x. ậ t p ch a  ẽ ậ ờ ể ọ ữ ệ ấ ọ

ươ

ữ ệ

27.10.2004

Ch

2

ấ ậ ờ

ng 7: C¸ác c u trúc d  li u  cho các t p r i nhau

ể ậ ờ 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

AKE­SET

ẽ ự ố ạ ủ

AKE­SET, UNION, và FIND­SET.

ờ –  n, s  các thao tác M –  m, s  t ng c ng các thao tác M ộ

ố ố ổ : ậ ª Nh n xét

ầ ọ ạ ộ – Sau n (cid:0)  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.ậ

ươ

ữ ệ

27.10.2004

Ch

3

ấ ậ ờ

ng 7: C¸ác c u trúc d  li u  cho các t p r i nhau

– m (cid:0) n.

ậ ờ

ộ ứ

ụ

ủ 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

ộ ồ ị ủ ầ ướ

ONNECTED­COMPONENTS xác đ nh các thành ph n liên

ị ng ầ ị – Th  t c C ủ ụ

ộ ồ ị ủ ướ 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.

v (cid:0) V[G]

E[G]

FIND­SET(v)

ươ

ữ ệ

27.10.2004

Ch

4

ấ ậ ờ

ng 7: C¸ác c u trúc d  li u  cho các t p r i nhau

CONNECTED­COMPONENTS(G) ỗ ỉ 1    for m i đ nh  2           do MAKE­SET(v) u, v) (cid:0) ỗ ạ 3    for m i c nh ( 4           do if FIND­SET(u) (cid:0) 5                    then UNION(u, v)

ậ ờ

ộ ứ

ụ

ủ

ế

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.

ươ

ữ ệ

27.10.2004

Ch

5

ấ ậ ờ

ng 7: C¸ác c u trúc d  li u  cho các t p r i nhau

SAME­COMPONENT(u, v) 1    if FIND­SET(u) = FIND­SET(v) 2         then return TRUE 3         else return FALSE

ậ ờ

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

6

ấ ậ ờ

ng 7: C¸ác c u trúc d  li u  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

ệ ủ ậ ầ ượ đ i di n c a t p. ng đ ng đ u đ

ế ứ ầ ử ạ c dùng làm ph n t ứ ng trong danh sách liên k t ch a

ứ ầ ử ế ế  k  ti p

ệ ủ ậ

ng ch a ph n t  đ i di n c a t p. ệ ủ ậ ỉ ế sách liên k tế ố ượ ° Đ i t ổ ố ượ ° M i đ i t – ph n t ầ ử ủ ậ  c a t p – con tr  ch  đ n đ i t ỏ ỉ ế ố ượ – con tr  ch  đ n ph n t ầ ử ạ ỏ ỉ ế ạ ° Con tr  ỏ head ch  đ n đ i di n c a t p. Con tr ỏ tail ch  đ n

ươ

ữ ệ

27.10.2004

Ch

7

ấ ậ ờ

ng 7: C¸ác c u trúc d  li u  cho các t p r i nhau

ầ ử ố ỉ ế  cu i trong danh sách. ph n t

ễ ậ

ể

ằ

ế 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

8

ấ ậ ờ

ng 7: C¸ác c u trúc d  li u  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

ệ

AKE­SET(x): t o m t danh sách liên k t ch  g m đ i

ạ ỉ ồ ế ố ộ

ệ ượ t ệ ệ ủ ậ ả ề ỏ ế ứ ạ ự – Hi n th c M ng  – Hi n th c F ự x. ự IND­SET(x): tr  v  con tr  đ n đ i di n c a t p ch a

x.

ệ ự

NION(x, y): ° g n danh sách c a  ậ ° c p nh t các con tr  c a các đ i t ỉ ế

ủ ủ y ủ x vào đuôi c a danh sách c a  ố ượ ủ

ỏ ủ ạ ầ ủ ứ

ươ

ữ ệ

27.10.2004

Ch

9

ấ ậ ờ

ng 7: C¸ác c u trúc d  li u  cho các t p r i nhau

– Hi n th c U ắ ậ 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.

ễ ậ

ế

ể

ế

ằ

Bi u di n t p b ng danh sách liên k t (ti p)

ª Ví dụ

ươ

ữ ệ

27.10.2004

Ch

10

ấ ậ ờ

ng 7: C¸ác c u trúc d  li u  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 2

ỗ ồ ố ượ n (cid:0)  1 thao tác lên n đ i t ầ (cid:0) ng mà c n (n2)

ờ ụ ộ th i gian.

ố ượ

ố

ượ ậ

Thao tác

S  các đ i t

ng đ

ậ c c p nh t

1 1

MAKE­SET(x1 ) MAKE­SET(x2 )

n

. . .

1

1 2 3

MAKE­SET(xn ) UNION(x1 , x2 ) UNION(x2 , x3 ) UNION(x3 , x4 )

(cid:0)

(n2)

. . .

n (cid:0)  1

UNION(xn (cid:0)  1 , xn )

ươ

ữ ệ

27.10.2004

Ch

11

ấ ậ ờ

ng 7: C¸ác c u trúc d  li u  cho các t p r i nhau

NION

ố ủ

ể

Heuristic đ  tăng t c c a U

ỏ ậ ª Nh n xét : Khi h p hai danh sách trong U

ệ ợ ủ ọ ượ ắ trong danh sách đ ỉ ế NION, m i con tr  (ch  đ n  c g n vào đuôi

ầ ử ả ượ ậ ậ ớ ạ đ i di n m i) c a các ph n t ủ c a danh sách kia ph i đ c c p nh t.

ủ ề ả ử ỗ ứ  s  m i danh sách có ch a thêm chi u dài c a nó.

Gi ª 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  ắ

ươ

ữ ệ

27.10.2004

Ch

12

ấ ậ ờ

ng 7: C¸ác c u trúc d  li u  cho các t p r i nhau

ủ ể ắ ắ ư ơ danh sách dài nh  nhau thì có th  g n tùy ý).

ợ

ọ

ố

Heuristic h p theo tr ng s

ª Ví dụ

ề chi u dài = 4

g

d

b

f

e

c

h

ươ

ữ ệ

27.10.2004

Ch

13

ấ ậ ờ

ng 7: C¸ác c u trúc d  li u  cho các t p r i nhau

ề chi u dài = 3

ễ ậ

ế

ể

ằ

ờ

ạ Bi u di n t p b ng danh sách liên k t: th i gian ch y

(Theorem 22.1)

ị ª Đ nh lý ằ ễ ế

ợ ồ ố ể ọ ậ ờ ộ

ờ n lg n) th i gian.

ứ

AKE­SET ch y trong th i gian

ạ ờ O(1)

ờ O(1)

NION: ờ

ạ ủ ờ

NION là th i gian t ng c ng

ị ờ ổ

ươ

ữ ệ

27.10.2004

Ch

14

ấ ậ ờ

ng 7: C¸ác c u trúc d  li u  cho các t p r i nhau

ầ ử ủ ệ ủ ậ ọ ầ ử ạ ầ ử 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 (cid:0) Ch ng minh – M i Mỗ – M i Fỗ IND­SET ch y trong th i gian  ạ – Xác đ nh th i gian ch y c a các thao tác U ạ ủ ° Th i gian ch y c a các thao tác U ấ l y trên m i ph n t ph n t ộ ỏ ỉ ế ậ  c a m i l n c p nh t con tr  ch  đ n   đó. ọ ầ ậ ứ  đ i di n c a t p ch a ph n t

ễ ậ

ể

ế

ằ

ờ

ạ Bi u di n t p b ng danh sách liên k t: th i gian ch y

ứ Ch ng minh

° Xét đ i t

ế ố ượ ấ ỳ ậ ờ (ti p theo) ng

ứ x

ằ ậ ộ ậ nhau. M i l n con tr  ch  đ n ph n t ượ ậ đ ấ ỳ ủ x b t k  trong m t t p b t k  c a các t p r i  ệ ủ ậ ầ ử ạ ỏ ỉ ế  đ i di n c a t p ch a  ỏ ơ ậ ả x ph i đã n m trong t p nh  h n ỗ ầ c c p nh t, thì

(cid:0) (cid:0)

ậ

ế

ậ

ả

ả

ấ

ầ

– 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

ậ

ế

ậ

ả

ả

ấ

ầ

– 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ử ầ tử – … – L n ầ k c p nh t con tr  c a  ậ

ả ỏ ủ x: t p k t qu  ph i có ít nh t 2

ấ k ph n ầ

.ử t ậ

Vì t p có nhi u l m là

ề ắ ậ ố ầ ậ n. V y s  l n c p

ậ ề ắ nh t con tr  c a ầ ử n ph n t  nên  k (cid:0) ỏ ủ x nhi u l m là

° Vì x là ph n t

ể ậ ậ ộ ờ

ỏ ủ

là  ủ

2k (cid:0)  lg n.  ổ ầ ử ấ ỳ  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 – Th i gian ch y t ng c ng c a dãy  ạ ổ ờ

ữ ệ

Ch

27.10.2004

ấ ậ ờ

m thao tác là: O(m) + O(n lg n)  15 = O(m + n lg n) . ầ ử O(n lg n). ộ ươ ng 7: C¸ác c u trúc d  li u  cho các t p r i nhau

ừ

ễ

ể

ằ

ậ ờ Bi u di n các t p r i nhau b ng r ng

ễ ừ ằ disjoint­set forest)

ễ ằ

ậ ờ ể ª Bi u di n các t p r i nhau b ng r ng ( – 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

ỏ ỉ ế ủ ộ

° 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

16

ấ ậ ờ

ng 7: C¸ác c u trúc d  li u  cho các t p r i nhau

ỗ   ngoài ra ỗ ố ủ ệ ủ ậ ứ ạ ứ ỗ ủ

ậ ờ

ừ

ế

ễ

ể

ằ

Bi u di n các t p r i nhau b ng r ng (ti p)

ª Ví dụ

b, c, e, h} và {d, f, g}. ệ ủ ậ – Hai cây sau bi u di n các t p { ậ ễ ể – c và f  l n l ầ ử ạ ầ ượ  đ i di n c a các t p { t là ph n t b, c, e, h} và {d, f,

ươ

ữ ệ

27.10.2004

Ch

17

ấ ậ ờ

ng 7: C¸ác c u trúc d  li u  cho các t p r i nhau

g}.

ậ ờ

ừ

ể

ễ

ằ

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 ạ

ậ ờ ừ ễ ể ằ

AKE­SET: t o m t cây ch  có m t nút.

ộ ộ ỉ

ỏ ỉ ế ệ ệ ự ự IND­SET b ng cách đu i theo các con tr  ch  đ n nút – Hi n th c M – Hi n th c F

ằ ượ

ượ ạ ườ đ ế cha cho đ n khi tìm đ ° Các nút đ ổ ố ủ c nút g c c a cây. ọ IND­SET t o thành c ghé qua khi g i F ẩ   ng d n

(find path). ự ệ ỉ ế ố ỏ ủ ố NION: làm cho con tr  c a g c cây này ch  đ n g c

ươ

ữ ệ

27.10.2004

Ch

18

ấ ậ ờ

ng 7: C¸ác c u trúc d  li u  cho các t p r i nhau

– Hi n th c U ủ c a cây kia.

ừ

ễ

ể

ằ

ậ ờ Bi u di n các t p r i nhau b ng r ng

ª Ví dụ

NION(e, g).

ả ủ ế – Hình (b) là k t qu  c a U

UNION

ươ

ữ ệ

27.10.2004

Ch

19

ấ ậ ờ

ng 7: C¸ác c u trúc d  li u  cho các t p r i nhau

ễ ậ

ể

ằ

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  ự ằ

ợ ự

NION:  (*)

ỗ đ  caoộ

ậ ớ rank = 0. ủ c a nút. M i nút đ

ỏ ơ ượ ợ ượ ° khi h p theo th  h ng hai cây, nút g c có rank nh  h n đ 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 U ộ rank. Rank là c n trên cho  ° duy trì cho m i nút m t  ở ạ ọ c kh i t o v i  ố ơ ớ rank l n h n.

làm thành con c a nút có  ườ ứ ạ ủ ng d n – Heuristic nén đ ẩ  (path compression).

ộ

ủ

ằ

ạ

ố

ộ

ườ

ơ

ng đi đ n

ế

ộ

(*) Đ  caoộ ấ ừ dài nh t t

c a m t nút trong m t cây là s  các c nh n m trên đ  nút đ n m t nút lá.

ươ

ữ ệ

27.10.2004

Ch

20

ấ ậ ờ

ng 7: C¸ác c u trúc d  li u  cho các t p r i nhau

ứ ạ

ợ

Heuristic h p theo th  h ng

ª Ví d : (s  bên c nh m i đ i t

ỗ ố ượ ụ ố ạ ng là ủ rank c a nó.)

1

1

0

b a b

UNION

0

0

0

c c a

2

d

1

1

c d

UNION

1

0

c f

0

0

e f

0

ươ

ữ ệ

27.10.2004

Ch

21

ấ ậ ờ

ng 7: C¸ác c u trúc d  li u  cho các t p r i nhau

e

ườ

Heuristic nén đ

ẫ ng d n

ườ ạ ng d n – Heuristic nén đ ẩ  (path compression). Ch y qua hai giai

IND­SET: ể

ạ ự

ố ủ ậ ườ đo n khi th c thi F ạ ° giai đo n ch y lên đ  tìm g c c a cây, ố ạ ° giai đo n ch y xu ng đ  c p nh t các nút trên đ ể ẩ ng d n đ

ươ

ữ ệ

27.10.2004

Ch

22

ấ ậ ờ

ng 7: C¸ác c u trúc d  li u  cho các t p r i nhau

ế ạ ể ậ ạ ố ỉ ự ế chúng ch  tr c ti p đ n g c.

ườ

ế

ẩ

Heuristic nén đ

ng d n (ti p)

ª Minh h a heuristic nén đ – Các hình tam giác t ượ

ọ ẫ ng d n do thao tác F

i các nút trong

ủ ườ IND­SET ố ạ ng tr ng các cây con có g c t hình (a). M i nút có con tr  ch  đ n nút cha c a nó.

ươ

ữ ệ

27.10.2004

Ch

23

ấ ậ ờ

ng 7: C¸ác c u trúc d  li u  cho các t p r i nhau

ự ỗ – Hình (b): sau khi th c thi F ư ỏ ỉ ế IND­SET(a)

ứ ạ

ợ

ườ

Các heuristic h p theo th  h ng và nén đ

ẩ ng d n

ª Các th  t c hi n th c các heuristics h p theo th  h ng và nén đ

ứ ạ ự ệ ợ ườ ng

ủ ụ AKE­SET, UNION, và FIND­SET

d n: Mẫ – Cha c a nút  ủ x là p[x].

MAKE­SET(x) 1    p[x] (cid:0)  x 2    rank[x] (cid:0)

0

UNION(x, y) 1    LINK(FIND­SET(x), FIND­SET(y))

rank[y]  x  y

rank[y]

rank[y] (cid:0)

1

LINK(x, y) 1    if rank[x] (cid:0) 2         then p[y] (cid:0) 3         else  p[x] (cid:0) 4                  if rank[x] (cid:0) 5                      then rank[y] (cid:0)

ươ

ữ ệ

27.10.2004

Ch

24

ấ ậ ờ

ng 7: C¸ác c u trúc d  li u  cho các t p r i nhau

ứ ạ

ợ

ườ

ế

ẩ

Các heuristics h p theo th  h ng và nén đ

ng d n (ti p)

p[x]

FIND­SET(p[x])

FIND­SET(x) 1    if x (cid:0) 2        then p[x] (cid:0) 3    return p[x]

ươ

ữ ệ

27.10.2004

Ch

25

ấ ậ ờ

ng 7: C¸ác c u trúc d  li u  cho các t p r i nhau

ưở

ủ

ờ

Aûnh h

ạ ng c a các heuristics lên th i gian ch y

ª Th i gian ch y

ờ ủ ồ m MAKE­SET, UNION,

°

ứ ạ ế ợ ộ ạ  c a m t dãy các thao tác g m  và FIND­SET, trong đó có n thao tác MAKE­SET: – N u ch  dùng heuristic h p theo th  h ng

IND­

ườ ẩ ỉ  O(m lg n) ỉ – N u ch  dùng heuristic nén đ ng d n, v i ố ớ f  là s  thao tác F

ế SET

(cid:0) (cid:0) n

(cid:0) (cid:0) n u ế f (cid:0) n u ế f (cid:0)

n ợ ứ ạ ườ – N u dùng heuristics h p theo th  h ng và nén đ ẩ ng d n

(f log(1 + f / n) n) (n + f lg n) c  haiả ế ° O(m (cid:0) (m, n))

ª

ọ ứ –  (cid:0) (m, n) là hàm đ o c a hàm Ackermann ả ủ – trong m i  ng d ng th c t ụ ự ế (cid:0) (m, n) (cid:0) , 4 .

ươ

ữ ệ

27.10.2004

Ch

26

ấ ậ ờ

ng 7: C¸ác c u trúc d  li u  cho các t p r i nhau

ứ ậ ệ ở (Không ch ng minh các ch n đã li t kê trên.)