›
›

Bài giảng Giải thuật - Chương 7: Các cấu trúc dữ liệu cho các tập rời nhau

Download
Caùc Caáu Truùc Döõ Lieäu cho caùc Taäp Rôøi Nhau  
27.10.2004  
1
Caùc thao taùc leân caáu truùc döõ lieäu caùc taäp rôøi nhau  
ª Caáu truùc döõ lieäu caùc taäp rôøi nhau ñöôïc ñònh nghóa bôûi  
– Moät taäp S cuûa caùc taäp ñoäng rôøi nhau, S = {S1 , S2 ,..., Sk}  
°
Moãi taäp Si ñöôïc töôïng tröng bôûi moät phaàn töû ñaïi dieän laø moät  
phaàn töû naøo ñoù cuûa noù.  
– Caùc thao taùc  
°
°
°
MAKE-SET(x): taïo moät taäp môùi chæ goàm x. Vì caùc taäp laø rôøi  
nhau neân x khoâng ñöôïc ñang naèm trong moät taäp khaùc.  
UNION(x, y): taïo taäp hoäi cuûa caùc taäp ñoäng Sx vaø Sy laàn löôït  
chöùa x vaø y, vôùi ñieàu kieän laø Sx vaø Sy laø rôøi nhau.  
FIND-SET(x): traû veà moät con troû chæ ñeán phaàn töû ñaïi dieän cuûa  
taäp chöùa x.  
ª Ñeå cho goïn, seõ duøng “caùc taäp rôøi nhau” ñeå goïi “caáu truùc döõ lieäu caùc  
taäp rôøi nhau”.  
27.10.2004  
2
Chöông 7: C¸aùc caáu truùc döõ lieäu cho  
caùc taäp rôøi nhau  
Caùc thao taùc leân caùc taäp rôøi nhau (tieáp)  
ª Phaân tích thôøi gian chaïy cuûa caùc thao taùc seõ döïa treân hai tham soá sau  
– n, soá caùc thao taùc MAKE-SET  
– m, soá toång coäng caùc thao taùc MAKE-SET, UNION, vaø FIND-SET.  
ª Nhaän xeùt:  
– Sau n − 1 laàn goïi UNION leân caùc taäp rôøi nhau thì coøn laïi ñuùng moät  
taäp.  
– m n.  
27.10.2004  
3
Chöông 7: C¸aùc caáu truùc döõ lieäu cho  
caùc taäp rôøi nhau  
Moät öùng duïng cuûa caùc taäp rôøi nhau  
ª Xaùc ñònh caùc thaønh phaàn lieân thoâng cuûa moät ñoà thò voâ höôùng  
– Thuû tuïc CONNECTED-COMPONENTS xaùc ñònh caùc thaønh phaàn lieân  
thoâng cuûa moät ñoà thò voâ höôùng.  
V[G] laø taäp caùc ñænh cuûa ñoà thò G, E[G] laø taäp caùc caïnh cuûa G.  
CONNECTED-COMPONENTS(G)  
1 for moãi ñænh v V[G]  
2
do MAKE-SET(v)  
3 for moãi caïnh (u, v) E[G]  
4
5
do if FIND-SET(u) FIND-SET(v)  
then UNION(u, v)  
27.10.2004  
4
Chöông 7: C¸aùc caáu truùc döõ lieäu cho  
caùc taäp rôøi nhau  
Moät öùng duïng cuûa caùc taäp rôøi nhau (tieáp)  
– Thuû tuïc SAME-COMPONENT xaùc ñònh hai ñænh coù cuøng moät thaønh  
phaàn lieân thoâng hay khoâng.  
SAME-COMPONENT(u, v)  
1 if FIND-SET(u) = FIND-SET(v)  
2
3
then return TRUE  
else return FALSE  
27.10.2004  
5
Chöông 7: C¸aùc caáu truùc döõ lieäu cho  
caùc taäp rôøi nhau  
Thao taùc leân caùc taäp rôøi nhau  
ª Ví duï: moät ñoà thò vôùi 4 thaønh phaàn lieân thoâng  
27.10.2004  
6
Chöông 7: C¸aùc caáu truùc döõ lieäu cho  
caùc taäp rôøi nhau  
Bieåu dieãn caùc taäp rôøi nhau duøng danh saùch lieân keát  
ª Bieåu dieãn caùc taäp rôøi nhau duøng danh saùch lieân keát (linked-list  
representation of disjoint sets):  
– Bieåu dieãn moåi taäp baèng moät danh saùch lieân keát. Trong moãi danh  
saùch lieân keát  
°
Ñoái töôïng ñöùng ñaàu ñöôïc duøng laøm phaàn töû ñaïi dieän cuûa taäp.  
Moåi ñoái töôïng trong danh saùch lieân keát chöùa  
– phaàn töû cuûa taäp  
°
– con troû chæ ñeán ñoái töôïng chöùa phaàn töû keá tieáp  
– con troû chæ ñeán phaàn töû ñaïi dieän cuûa taäp.  
°
Con troû head chæ ñeán ñaïi dieän cuûa taäp. Con troû tail chæ ñeán  
phaàn töû cuoái trong danh saùch.  
27.10.2004  
7
Chöông 7: C¸aùc caáu truùc döõ lieäu cho  
caùc taäp rôøi nhau  
Bieåu dieãn taäp baèng danh saùch lieân keát  
ª Ví duï  
head  
tail  
head  
tail  
27.10.2004  
8
Chöông 7: C¸aùc caáu truùc döõ lieäu cho  
caùc taäp rôøi nhau  
Bieåu dieãn taäp baèng danh saùch lieân keát (tieáp)  
ª Hieän thöïc caùc thao taùc  
– Hieän thöïc MAKE-SET(x): taïo moät danh saùch lieân keát chæ goàm ñoái  
töôïng x.  
– Hieän thöïc FIND-SET(x): traû veà con troû ñeán ñaïi dieän cuûa taäp chöùa x.  
– Hieän thöïc UNION(x, y):  
°
gaén danh saùch cuûa x vaøo ñuoâi cuûa danh saùch cuûa y  
°
caäp nhaät caùc con troû cuûa caùc ñoái töôïng trong danh saùch cuõ cuûa  
x ñeå chuùng chæ ñeán ñaïi dieän cuûa taäp, töùc laø ñaàu cuûa danh saùch  
cuõ cuûa y.  
27.10.2004  
9
Chöông 7: C¸aùc caáu truùc döõ lieäu cho  
caùc taäp rôøi nhau  
Bieåu dieãn taäp baèng danh saùch lieân keát (tieáp)  
ª Ví duï  
27.10.2004  
10  
Chöông 7: C¸aùc caáu truùc döõ lieäu cho  
caùc taäp rôøi nhau  
Thao taùc UNION khoâng duøng heuristic  
ª Ví duï moät chuoãi goàm 2n − 1 thao taùc leân n ñoái töôïng maø caàn (n2)  
thôøi gian.  
Thao taùc  
Soá caùc ñoái töôïng ñöôïc caäp nhaät  
MAKE-SET(x1 )  
1
1
MAKE-SET(x2 )  
.
n
.
.
MAKE-SET(xn )  
1
1
2
3
UNION(x1 , x2 )  
UNION(x2 , x3 )  
UNION(x3 , x4 )  
(n2)  
.
.
.
UNION(xn − 1 , xn )  
n − 1  
27.10.2004  
11  
Chöông 7: C¸aùc caáu truùc döõ lieäu cho  
caùc taäp rôøi nhau  
Heuristic ñeå taêng toác cuûa UNION  
ª Nhaän xeùt: Khi hôïp hai danh saùch trong UNION, moïi con troû (chæ ñeán  
ñaïi dieän môùi) cuûa caùc phaàn töû trong danh saùch ñöôïc gaén vaøo ñuoâi  
cuûa danh saùch kia phaûi ñöôïc caäp nhaät.  
Giaû söû moãi danh saùch coù chöùa theâm chieàu daøi cuûa noù.  
ª Heuristic hôïp theo troïng soá (weighted-union heuristic): khi hôïp hai  
danh saùch  
– gaén danh saùch ngaén hôn vaøo ñuoâi cuûa danh saùch daøi hôn (neáu caùc  
danh saùch daøi nhö nhau thì coù theå gaén tuøy yù).  
27.10.2004  
12  
Chöông 7: C¸aùc caáu truùc döõ lieäu cho  
caùc taäp rôøi nhau  
Heuristic hôïp theo troïng soá  
ª Ví duï  
chieàu daøi = 4  
chieàu daøi = 3  
g
d
b
f
e
c
h
27.10.2004  
13  
Chöông 7: C¸aùc caáu truùc döõ lieäu cho  
caùc taäp rôøi nhau  
Bieåu dieãn taäp baèng danh saùch lieân keát: thôøi gian chaïy  
ª Ñònh lyù (Theorem 22.1)  
Baèng caùch duøng bieåu dieãn danh saùch lieân keát cho caùc taäp rôøi nhau vaø  
heuristic hôïp theo troïng soá (weighted-union heuristic), moät daõy goàm  
coù m thao taùc MAKE-SET, UNION, vaø FIND-SET, trong ñoù coù n thao taùc  
laø MAKE-SET, toán O(m + n lg n) thôøi gian.  
Chöùng minh  
– Moãi MAKE-SET chaïy trong thôøi gian O(1)  
– Moãi FIND-SET chaïy trong thôøi gian O(1)  
– Xaùc ñònh thôøi gian chaïy cuûa caùc thao taùc UNION:  
°
Thôøi gian chaïy cuûa caùc thao taùc UNION laø thôøi gian toång coäng  
laáy treân moïi phaàn töû cuûa moïi laàn caäp nhaät con troû chæ ñeán  
phaàn töû ñaïi dieän cuûa taäp chöùa phaàn töû ñoù.  
27.10.2004  
14  
Chöông 7: C¸aùc caáu truùc döõ lieäu cho  
caùc taäp rôøi nhau  
Bieåu dieãn taäp baèng danh saùch lieân keát: thôøi gian chaïy  
Chöùng minh (tieáp theo)  
°
Xeùt ñoái töôïng x baát kyø trong moät taäp baát kyø cuûa caùc taäp rôøi  
nhau. Moãi laàn con troû chæ ñeán phaàn töû ñaïi dieän cuûa taäp chöùa x  
ñöôïc caäp nhaät, thì x phaûi ñaõ naèm trong taäp nhoû hôn  
– Laàn 1 caäp nhaät con troû cuûa x: taäp keát quaû phaûi coù ít nhaát 2 phaàn töû  
– Laàn 2 caäp nhaät con troû cuûa x: taäp keát quaû phaûi coù ít nhaát 4 phaàn töû  
– …  
– Laàn k caäp nhaät con troû cuûa x: taäp keát quaû phaûi coù ít nhaát 2k phaàn  
töû.  
Vì taäp coù nhieàu laém laø n phaàn töû neân 2k n. Vaäy soá laàn caäp  
nhaät con troû cuûa x nhieàu laém laø k lg n.  
°
Vì x laø phaàn töû baát kyø neân thôøi gian toång coäng ñeå caäp nhaät caùc  
con troû cuûa moïi phaàn töû laø O(n lg n).  
– Thôøi gian chaïy toång coäng cuûa daõy m thao taùc laø: O(m) + O(n lg n)  
= O(m + n lg n) .  
27.10.2004  
15  
Chöông 7: C¸aùc caáu truùc döõ lieäu cho  
caùc taäp rôøi nhau  
Bieåu dieãn caùc taäp rôøi nhau baèng röøng  
ª Bieåu dieãn caùc taäp rôøi nhau baèng röøng (disjoint-set forest)  
– Bieåu dieãn moãi taäp baèng moät caây coù goác:  
°
Moãi nuùt cuûa caây chöùa moät phaàn töû cuûa taäp  
ngoaøi ra  
°
°
Moãi nuùt chöùa moät con troû chæ ñeán cha cuûa noù  
Goác cuûa moãi caây chöùa ñaïi dieän cuûa taäp vaø laø cha cuûa chính noù.  
27.10.2004  
16  
Chöông 7: C¸aùc caáu truùc döõ lieäu cho  
caùc taäp rôøi nhau  
Bieåu dieãn caùc taäp rôøi nhau baèng röøng (tieáp)  
ª Ví duï  
– Hai caây sau bieåu dieãn caùc taäp {b, c, e, h} vaø {d, f, g}.  
– c vaø f laàn löôït laø phaàn töû ñaïi dieän cuûa caùc taäp {b, c, e, h} vaø {d, f,  
g}.  
27.10.2004  
17  
Chöông 7: C¸aùc caáu truùc döõ lieäu cho  
caùc taäp rôøi nhau  
Bieåu dieãn caùc taäp rôøi nhau baèng röøng: caùc thao taùc  
ª Caùc thao taùc leân caùc taäp rôøi nhau khi bieåu dieãn baèng röøng  
– Hieän thöïc MAKE-SET: taïo moät caây chæ coù moät nuùt.  
– Hieän thöïc FIND-SET baèng caùch ñuoåi theo caùc con troû chæ ñeán nuùt  
cha cho ñeán khi tìm ñöôïc nuùt goác cuûa caây.  
°
Caùc nuùt ñöôïc gheù qua khi goïi FIND-SET taïo thaønh ñöôøng daån  
(find path).  
– Hieän thöïc UNION: laøm cho con troû cuûa goác caây naøy chæ ñeán goác  
cuûa caây kia.  
27.10.2004  
18  
Chöông 7: C¸aùc caáu truùc döõ lieäu cho  
caùc taäp rôøi nhau  
Bieåu dieãn caùc taäp rôøi nhau baèng röøng  
ª Ví duï  
– Hình (b) laø keát quaû cuûa UNION(e, g).  
UNION  
27.10.2004  
19  
Chöông 7: C¸aùc caáu truùc döõ lieäu cho  
caùc taäp rôøi nhau  
Bieåu dieãn taäp baèng caây  
ª Duøng hai heuristics ñeå giaûm thôøi gian chaïy cuûa caùc daõy caùc thao taùc  
leân caùc taäp rôøi nhau khi hieän thöïc baèng röøng:  
– Heuristic hôïp theo thöù haïng (union by rank) khi thöïc thi UNION:  
°
duy trì cho moãi nuùt moät rank. Rank laø caän treân cho ñoä cao (*)  
cuûa nuùt. Moïi nuùt ñöôïc khôûi taïo vôùi rank = 0.  
°
khi hôïp theo thöù haïng hai caây, nuùt goác coù rank nhoû hôn ñöôïc  
laøm thaønh con cuûa nuùt coù rank lôùn hôn.  
– Heuristic neùn ñöôøng daån (path compression).  
(*) Ñoä cao cuûa moät nuùt trong moät caây laø soá caùc caïnh naèm treân ñöôøng ñi ñôn  
daøi nhaát töø nuùt ñeán moät nuùt laù.  
27.10.2004  
20  
Chöông 7: C¸aùc caáu truùc döõ lieäu cho  
caùc taäp rôøi nhau  
Tải về để xem bản đầy đủ
ppt 26 trang Thùy Anh 27/04/2022 5460
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Giải thuật - Chương 7: Các cấu trúc dữ liệu cho các tập rời nhau", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • pptbai_giang_giai_thuat_chuong_7_cac_cau_truc_du_lieu_cho_cac_t.ppt