Bài giảng Phân tích thiết kế giải thuật - Chương 9: Cây khung nhỏ nhất

14 
2 
4 
7 
6 
11 
8 
S  
V  S  
13.11.2004 
7 
Ch. 9: Cay khung nho nhat 
Cạnh nhẹ (light edge) 
Các khái niệm quan trọng (tiếp) 
Một phép cắt bảo toàn tập các cạnh A ( respects A ) nếu không có cạnh nào của A xuyên qua phép cắt. 
Một cạnh là một cạnh nhẹ vượt qua phép cắt nếu trọng số của nó là nhỏ nhất trong mọi trọng số của các cạnh xuyên qua phép cắt. Ví dụ: cạnh ( c , d ). 
b 
f 
c 
d 
h 
g 
i 
a 
e 
8 
7 
9 
10 
1 
2 
4 
14 
2 
4 
7 
6 
11 
8 
S  
V  S  
13.11.2004 
8 
Ch. 9: Cay khung nho nhat 
Nhận ra một cạnh an toàn 
Định lý 24.1 
Cho 
G = ( V , E ) là một đồ thị liên thông, vô hướng 
w là một hàm trọng số trên E 
A là một tập con của một cây khung nhỏ nhất cho G 
( S , V  S ) là một phép cắt bất kỳ của G bảo toàn A 
( u , v ) là một cạnh nhẹ vượt qua ( S , V  S ) 
	 cạnh ( u , v ) là an toàn cho A . 
Chứng minh 
13.11.2004 
9 
Ch. 9: Cay khung nho nhat 
Nhận ra một cạnh an toàn 
(tiếp) 
S : tập các đỉnh đen, V  S : tập các đỉnh trắng 
Các cạnh của một cây khung nhỏ nhất T được vẽ ra trong hình, còn các cạnh của G thì không 
A : tập các cạnh xám 
Cạnh ( u , v ) là cạnh nhẹ xuyên qua phép cắt ( S , V  S ). 
p là đường đi duy nhất từ u đến v trong T . 
x 
u 
y 
v 
p 
13.11.2004 
10 
Ch. 9: Cay khung nho nhat 
Nhận ra một cạnh an toàn 
(tiếp) 
Định nghĩa cây khung T’ = T - ( x , y )  ( u , v ) 
T’ là cây khung nhỏ nhất vì 
w ( T’ ) = w ( T ) - w ( x , y ) + w ( u , v ) 
  w ( T ),	vì w ( u , v )  w ( x , y ) 
( u , v ) là an toàn cho A vì A  ( u , v )  T’ . 
x 
u 
y 
v 
p 
13.11.2004 
11 
Ch. 9: Cay khung nho nhat 
Nhận ra một cạnh an toàn (tiếp) 
Hệ luận 24.2 
Cho 
G = ( V , E ) là một đồ thị liên thông, vô hướng với một hàm trọng số w trên E 
A là một tập con của E sao cho A nằm trong một cây khung nhỏ nhất cho G 
 C = ( V C , E C ) là một thành phần liên thông (cây) trong rừng G A = ( V , A ). 
	Thì, 
nếu ( u , v ) là một cạnh nhẹ nối C với một thành phần khác trong G A 
	  ( u , v ) là an toàn cho A . 
	 Chứng minh 
Phép cắt ( V C , V - V C ) bảo toàn A , do đó ( u , v ) là một cạnh nhẹ đối với phép cắt này. 
13.11.2004 
12 
Ch. 9: Cay khung nho nhat 
Giải thuật của Kruskal 
Giải thuật của Kruskal 
dựa trên giải thuật G ENERIC -MST, mà A ban đầu là một rừng mà mỗi cây chỉ chứa một đỉnh của G . 
mỗi tập rời nhau chứa các đỉnh của một cây trong rừng hiện thời. 
MST-K RUSKAL ( G , w ) 
1	 A   
2	 for mỗi đỉnh v  V [ G ] 
3	 do M AKE -S ET ( v ) 
4	xếp các cạnh  E theo thứ tự trọng số w không giảm 
5	 for mỗi cạnh ( u , v )  E, theo thứ tự trọng số không giảm 
6	 do if F IND -S ET ( u )  F IND -S ET ( v ) 
7	 then A  A  {( u , v )} 
8	 U NION ( u , v ) 
9	 return A 
13.11.2004 
13 
Ch. 9: Cay khung nho nhat 
Thực thi giải thuật của Kruskal 
b 
f 
c 
d 
h 
g 
i 
a 
e 
8 
7 
9 
10 
1 
2 
4 
14 
2 
4 
7 
6 
11 
8 
b 
f 
c 
d 
h 
g 
i 
a 
e 
8 
7 
9 
10 
1 
2 
4 
14 
2 
4 
7 
6 
11 
8 
(a) 
(b) 
1 
2 
2 
4 
4 
6 
7 
7 
8 
8 
9 
10 
11 
14 
Các cạnh được xếp theo thứ tự trọng số không giảm: 
13.11.2004 
14 
Ch. 9: Cay khung nho nhat 
Thực thi giải thuật của Kruskal (tiếp) 
b 
f 
c 
d 
h 
g 
i 
a 
e 
8 
7 
9 
10 
1 
2 
4 
14 
2 
4 
7 
6 
11 
8 
b 
f 
c 
d 
h 
g 
i 
a 
e 
8 
7 
9 
10 
1 
2 
4 
14 
2 
4 
7 
6 
11 
8 
(d) 
(c) 
1 
2 
2 
4 
4 
6 
7 
7 
8 
8 
9 
10 
11 
14 
13.11.2004 
15 
Ch. 9: Cay khung nho nhat 
Thực thi giải thuật của Kruskal (tiếp) 
b 
f 
c 
d 
h 
g 
i 
a 
e 
8 
7 
9 
10 
1 
2 
4 
14 
2 
4 
7 
6 
11 
8 
b 
f 
c 
d 
h 
g 
i 
a 
e 
8 
7 
9 
10 
1 
2 
4 
14 
2 
4 
7 
6 
11 
8 
b 
f 
c 
d 
h 
g 
i 
a 
e 
8 
7 
9 
10 
1 
2 
4 
14 
2 
4 
7 
6 
11 
8 
b 
f 
c 
d 
h 
g 
i 
a 
e 
8 
7 
9 
10 
1 
2 
4 
14 
2 
4 
7 
6 
11 
8 
(e) 
(f) 
(h) 
(g) 
13.11.2004 
16 
Ch. 9: Cay khung nho nhat 
Thực thi giải thuật của Kruskal (tiếp) 
b 
f 
c 
d 
h 
g 
i 
a 
e 
8 
7 
9 
10 
1 
2 
4 
14 
2 
4 
7 
6 
11 
8 
b 
f 
c 
d 
h 
g 
i 
a 
e 
8 
7 
9 
10 
1 
2 
4 
14 
2 
4 
7 
6 
11 
8 
b 
f 
c 
d 
h 
g 
i 
a 
e 
8 
7 
9 
10 
1 
2 
4 
14 
2 
4 
7 
6 
11 
8 
b 
f 
c 
d 
h 
g 
i 
a 
e 
8 
7 
9 
10 
1 
2 
4 
14 
2 
4 
7 
6 
11 
8 
(i) 
(j) 
(l) 
(k) 
13.11.2004 
17 
Ch. 9: Cay khung nho nhat 
Thực thi giải thuật của Kruskal (tiếp) 
b 
f 
c 
d 
h 
g 
i 
a 
e 
8 
7 
9 
10 
1 
2 
4 
14 
2 
4 
7 
6 
11 
8 
b 
f 
c 
d 
h 
g 
i 
a 
e 
8 
7 
9 
10 
1 
2 
4 
14 
2 
4 
7 
6 
11 
8 
(n) 
(m) 
1 
2 
2 
4 
4 
6 
7 
7 
8 
8 
9 
10 
11 
14 
13.11.2004 
18 
Ch. 9: Cay khung nho nhat 
Phân tích giải thuật của Kruskal 
Dùng cấu trúc dữ liệu các tập rời nhau (disjoint sets), chương 22, với các heuristics 
Hợp theo thứ hạng (union-by-rank) 
Nén đường dẫn (path-compression). 
Nhận xét (cần đến khi đánh giá thời gian chạy) 
Giải thuật gọi  V  lần M AKE -S ET và gọi tổng cộng O ( E ) lần các thao tác M AKE -S ET , U NION , F IND -S ET . 
Vì G liên thông nên | E |  | V | - 1. 
13.11.2004 
19 
Ch. 9: Cay khung nho nhat 
Phân tích giải thuật của Kruskal (tiếp) 
Thời gian chạy của MST-K RUSKAL gồm 
Khởi động: O ( V ) 
Sắp xếp ở dòng 4: O ( E lg E ) 
Dòng 5-8: O ( E ( E , V )) (xem nhận xét), 
= O ( E lg E ) vì ( E , V ) = O ( lg E ). 
Vậy thời gian chạy của MST-K RUSKAL là O ( E lg E ). 
13.11.2004 
20 
Ch. 9: Cay khung nho nhat 
Giải thuật của Prim 
Giải thuật của Prim 
dựa trên giải thuật G ENERIC -MST, ở đây A là một cây duy nhất 
trong khi thực thi giải thuật 
A = {( v , p [ v ]) : v  V - { r } - Q } 
khi giải thuật xong, Q = , nên 
A = {( v , p [ v ]) : v  V - { r } } 
13.11.2004 
21 
Ch. 9: Cay khung nho nhat 
Giải thuật của Prim (tiếp) 
Tập V - Q chứa các đỉnh của cây đang được nuôi lớn. 
MST-P RIM ( G , w , r ) 
 1	 Q  V [ G ] 
 2	 for mỗi đỉnh u  Q 
 3	 do key [ u ]   
 4	 key [ r ]  0 
 5	 p [ r ]  NIL 
 6	 while Q   
 7	 do u  E XTRACT -M IN ( Q ) 
 8	 for mỗi đỉnh v  Adj [ u ] 
 9	 do if v  Q và w ( u , v ) < key [ v ] 
10	 then p [ v ]  u 
11	 key [ v ]  w ( u , v ) 
 r : gốc của cây khung nhỏ 
 nhất sẽ trả về 
 Q : priority queue mà khóa 
 là trường key 
  [ v ] : đỉnh cha mẹ của v . 
13.11.2004 
22 
Ch. 9: Cay khung nho nhat 
Thực thi giải thuật của Prim 
b 
f 
c 
d 
h 
g 
i 
a 
e 
8 
7 
9 
10 
1 
2 
4 
14 
2 
4 
7 
6 
11 
8 
 
 
 
 
 
 
 
 
0 
Sau khi khởi động: 
(các số bên mỗi đỉnh là trị của key của đỉnh) 
13.11.2004 
23 
Ch. 9: Cay khung nho nhat 
Thực thi giải thuật của Prim (tiếp) 
b 
f 
c 
d 
h 
g 
i 
a 
e 
8 
7 
9 
10 
1 
2 
4 
14 
2 
4 
7 
6 
11 
8 
b 
f 
c 
d 
h 
g 
i 
a 
e 
8 
7 
9 
10 
1 
2 
4 
14 
2 
4 
7 
6 
11 
8 
(a) 
(b) 
 
4 
8 
 
 
8 
8 
 
 
 
 
 
 
 
 
Sau lần lặp 1: 
Sau lần lặp 2: 
Các đỉnh còn trong Q màu trắng, các đỉnh đã được đưa ra khỏi Q màu đen 
13.11.2004 
24 
Ch. 9: Cay khung nho nhat 
Thực thi giải thuật của Prim (tiếp) 
b 
f 
c 
d 
h 
g 
i 
a 
e 
8 
7 
9 
10 
1 
2 
4 
14 
2 
4 
7 
6 
11 
8 
b 
f 
c 
d 
h 
g 
i 
a 
e 
8 
7 
9 
10 
1 
2 
4 
14 
2 
4 
7 
6 
11 
8 
(c) 
(d) 
2 
7 
 
4 
 
8 
7 
6 
7 
 
4 
Sau lần lặp 3: 
Sau lần lặp 4: 
13.11.2004 
25 
Ch. 9: Cay khung nho nhat 
Thực thi giải thuật của Prim (tiếp) 
b 
f 
c 
d 
h 
g 
i 
a 
e 
8 
7 
9 
10 
1 
2 
4 
14 
2 
4 
7 
6 
11 
8 
b 
f 
c 
d 
h 
g 
i 
a 
e 
8 
7 
9 
10 
1 
2 
4 
14 
2 
4 
7 
6 
11 
8 
(e) 
(f) 
b 
f 
c 
d 
h 
g 
i 
a 
e 
8 
7 
9 
10 
1 
2 
4 
14 
2 
4 
7 
6 
11 
8 
b 
f 
c 
d 
h 
g 
i 
a 
e 
8 
7 
9 
10 
1 
2 
4 
14 
2 
4 
7 
6 
11 
8 
(g) 
(h) 
Sau lần lặp 5: 
Sau lần lặp 6: 
Sau lần lặp 7: 
Sau lần lặp 8: 
13.11.2004 
26 
Ch. 9: Cay khung nho nhat 
Thực thi giải thuật của Prim (tiếp) 
b 
f 
c 
d 
h 
g 
i 
a 
e 
8 
7 
9 
10 
1 
2 
4 
14 
2 
4 
7 
6 
11 
8 
(i) 
Sau lần lặp 9: 
13.11.2004 
27 
Ch. 9: Cay khung nho nhat 
Phân tích giải thuật của Prim 
Thời gian chạy của MST-P RIM tùy thuộc vào cách hiện thực priority queue Q 
Trường hợp hiện thực Q là binary heap 
Khởi tạo trong dòng 1-4 dùng B UILD- H EAP tốn O ( V ) thời gian 
Vòng while được lặp  V  lần, mỗi E XTRACT -M IN tốn O (lg V ) thời gian. Như vậy các lần gọi E XTRACT -M IN tốn tất cả O ( V lg V ) thời gian. 
Vòng for được lặp O ( E ) lần, trong vòng lặp này dòng 11 (dùng H EAPIFY ) tốn O (lg V ) thời gian. 
Vậy thời gian chạy tổng cộng của MST-P RIM là O ( V lg V + E lg V ) = O ( E lg V ). 
13.11.2004 
28 
Ch. 9: Cay khung nho nhat 
Phân tích giải thuật của Prim (tiếp) 
Trường hợp hiện thực Q là Fibonacci heap 
Khởi tạo trong dòng 1- 4 dùng M AKE -F IB -H EAP và F IB -H EAP -I NSERT tốn O ( V ) amortized time 
Mỗi F IB -H EAP -E XTRACT -M IN tốn O (lg V ) amortized time 
Mỗi thao tác F IB -H EAP -D ECREASE -K EY cần để hiện thực dòng 11 tốn O (1) amortized time 
Vậy thời gian chạy tổng cộng của MST-P RIM là O ( E + V lg V ). 
13.11.2004 
29 
Ch. 9: Cay khung nho nhat