Bài giảng Phân tích thiết kế giải thuật - Chương 8: Giải thuật tìm kiếm trong đồ thị

nên một rừng theo chiều sâu , gồm nhiều cây theo chiều sâu . 
Các cạnh trong E p được gọi là các cạnh cây . 
7.11.2004 
23 
Ch. 8: Elementary Graph Algorithms 
Tìm kiếm theo chiều sâu 
 Trong khi tìm kiếm, các đỉnh được tô màu để chỉ ra trạng thái của nó 
khởi đầu: màu trắng 
được tìm ra ( discovered ): màu xám 
hoàn tất , xong ( finished ): màu đen 
Mỗi đỉnh v được ghi giờ ( timestamp) , có hai timestamps 
 d [ v ]: ( d iscovered) đỉnh v được tìm ra, sơn v xám 
 f [ v ]: ( f inished) hoàn tất việc thăm dò từ đỉnh v , sơn v đen. 
7.11.2004 
24 
Ch. 8: Elementary Graph Algorithms 
Tìm kiếm theo chiều sâu 
Một đồ thị G = ( V, E ) vô hướng hay có hướng 
biểu diễn dùng danh sách kề 
biến toàn cục time : dùng cho timestamp 
Mỗi u  V 
color [ u ]: WHITE , GREY , BLACK 
d [ u ] : thời điểm đỉnh u được tìm ra 
f [ u ] : thời điểm hoàn tất thăm dò từ đỉnh u 
 [ u ] : con trỏ chỉ đến cha mẹ của u . 
7.11.2004 
25 
Ch. 8: Elementary Graph Algorithms 
Tìm kiếm theo chiều sâu 
DFS( G ) 
1	 for each vertex u  V [ G ] 
2	 do color [ u ]  WHITE 
3	 p [ u ]  NIL 
4	 time  0 
5	 for each vertex u  V [ G ] 
6	 do if color [ u ] = WHITE 
7	 then DFS-V ISIT ( u ) 
DFS-V ISIT ( u ) 
1	 color [ u ]  GRAY 
2	 d [ u ]  time  time + 1 
3	 for each v  Adj [ u ] 
4	 do if color [ v ] = WHITE 
5	 then p [ v ]  u 
6	 DFS-V ISIT ( v ) 
7	 color [ u ]  BLACK 
8	 f [ u ]  time  time + 1 
7.11.2004 
26 
Ch. 8: Elementary Graph Algorithms 
Thao tác của DFS lên đồ thị -- Ví dụ 
1/ 
v 
w 
u 
y 
z 
x 
1/ 
2/ 
v 
w 
u 
y 
z 
x 
(a) 
(b) 
1/ 
2/ 
3/ 
v 
w 
u 
y 
z 
x 
(c) 
1/ 
2/ 
3/ 
v 
w 
u 
y 
z 
x 
(d) 
7.11.2004 
27 
Ch. 8: Elementary Graph Algorithms 
Thao tác của DFS lên đồ thị -- Ví dụ (tiếp theo) 
1/ 
2/ 
4/ 
3/ 
v 
w 
u 
y 
z 
x 
(e) 
1/ 
2/ 
4/5 
3/ 
v 
w 
u 
y 
z 
x 
(f) 
1/ 
2/ 
4/5 
3/6 
v 
w 
u 
y 
z 
x 
(g) 
1/ 
2/7 
4/5 
3/6 
v 
w 
u 
y 
z 
x 
(h) 
B 
B 
B 
B 
7.11.2004 
28 
Ch. 8: Elementary Graph Algorithms 
Thao tác của DFS lên đồ thị -- Ví dụ (tiếp theo) 
1/ 
2/7 
4/5 
3/6 
v 
w 
u 
y 
z 
x 
(i) 
1/8 
2/7 
4/5 
3/6 
v 
w 
u 
y 
z 
x 
(j) 
1/8 
2/7 
9/ 
4/5 
3/6 
v 
w 
u 
y 
z 
x 
(k) 
1/8 
2/7 
9/ 
4/5 
3/6 
v 
w 
u 
y 
z 
x 
(l) 
B 
B 
F 
F 
B 
F 
B 
F 
C 
7.11.2004 
29 
Ch. 8: Elementary Graph Algorithms 
Thao tác của DFS lên đồ thị -- Ví dụ (tiếp theo) 
1/8 
2/7 
9/ 
4/5 
3/6 
10/ 
v 
w 
u 
y 
z 
x 
(m) 
1/8 
2/7 
9/ 
4/5 
3/6 
10/ 
v 
w 
u 
y 
z 
x 
(n) 
1/8 
2/7 
9/ 
4/5 
3/6 
10/11 
v 
w 
u 
y 
z 
x 
(o) 
1/8 
2/7 
9/12 
4/5 
3/6 
10/11 
v 
w 
u 
y 
z 
x 
(p) 
B 
F 
C 
B 
F 
C 
B 
F 
C 
B 
F 
C 
B 
B 
B 
7.11.2004 
30 
Ch. 8: Elementary Graph Algorithms 
Phân tích DFS 
Thời gian chạy của DFS là ( V + E ) vì 
Các vòng lặp trong DFS cần ( V ) thời gian, chưa kể thời gian thực thi các lần gọi DFS-V ISIT . 
DFS-V ISIT được gọi đúng một lần cho mỗi đỉnh v (vì ngay khi đó màu đỉnh v  xám). 
Thực thi DFS-V ISIT ( v ): danh sách kề của v được duyệt. 
Vậy thời gian để duyệt tất cả các danh sách kề là ( E ). 
7.11.2004 
31 
Ch. 8: Elementary Graph Algorithms 
Đặc tính của tìm kiếm theo chiều sâu 
Định lý 23.6	Định lý dấu ngoặc, Parenthesis theorem 
Trong mọi tìm kiếm theo chiều sâu của một đồ thị hữu hướng hay vô hướng G = ( V , E ), đối với mọi cặp đỉnh u và v , chỉ một trong ba điều sau là đúng 
các khoảng [ d [ u ], f [ u ]] và [ d [ v ], f [ v ]] là rời nhau, 
khoảng [ d [ u ], f [ u ]] hoàn toàn nằm trong khoảng [ d [ v ], f [ v ]], và u là một hậu duệ của v trong cây theo chiều sâu, 
khoảng [ d [ v ], f [ v ]] hoàn toàn nằm trong khoảng [ d [ u ], f [ u ]], và v là một hậu duệ của u trong cây theo chiều sâu. 
Chứng minh 
Trường hợp d [ u ] < d [ v ]: xét hai trường hợp con 
d [ v ] < f [ u ]. Đỉnh v được tìm ra trong khi u còn là xám, vậy v là một hậu duệ của u . Hơn nữa vì v được tìm ra sau u , nên một khi mọi cạnh từ v được thăm dò xong thì v hoàn tất, trước khi việc tìm 
7.11.2004 
32 
Ch. 8: Elementary Graph Algorithms 
Đặc tính của tìm kiếm theo chiều sâu 
Chứng minh (tiếp) 
kiếm quay về u và hoàn tất u , do đó f [ v ] < f [ u ]. Tổng kết: 
d [ u ] < d [ v ] < f [ v ] < f [ u ], tức là khoảng [ d [ v ], f [ v ]] hoàn toàn nằm trong khoảng [ d [ u ], f [ u ]]. 
f [ u ] < d [ v ]. Hơn nữa, vì d [ u ] < f [ u ] và d [ v ] < f [ v ] nên d [ u ] < f [ u ] < d [ v ] < f [ v ], tức là các khoảng [ d [ u ], f [ u ]] và [ d [ v ], f [ v ]] là rời nhau. 
Trường hợp d [ v ] < d [ u ]. Tương tự. 
7.11.2004 
33 
Ch. 8: Elementary Graph Algorithms 
Đặc tính của tìm kiếm theo chiều sâu 
Định lý 23.8	Định lý white-path 
Cho một đồ thị vô hướng hay có hướng G = ( V , E ). 
Trong rừng theo chiều sâu của G , đỉnh v là một hậu duệ của đỉnh u 
 vào thời điểm d [ u ] khi DFS tìm ra u , đỉnh v có thể đến được từ u theo một đường đi chỉ gồm các đỉnh màu trắng. 
Chứng minh 
 : Giả sử v là một hậu duệ của đỉnh u . Gọi w là một đỉnh bất kỳ nằm trên đường đi từ u đến v trong cây theo chiều sâu, thì w là một hậu duệ của u . Vậy d [ u ] < d [ w ], do đó w là trắng vào lúc d [ u ]. 
 : (sketch) d [ u ] < d [ v ] < f [ v ] < f [ u ]. 
7.11.2004 
34 
Ch. 8: Elementary Graph Algorithms 
Đặc tính của tìm kiếm theo chiều sâu 
Phân loại các cạnh của G = ( V , E ) 
Các cạnh cây ( tree edge): là các cạnh trong G p . 
Các cạnh lùi ( back edge): là các cạnh ( u , v ) nối u đến một nút tổ tiên (ancestor) v trong một depth-first tree. 
Các cạnh tiến ( forward edge): là các cạnh, không phải là các cạnh cây, ( u , v ) nối một đỉnh u đến một hậu duệ (descendant) v trong một depth-first tree. 
Các cạnh xuyên ( cross edge): là tất cả các cạnh còn lại. 
7.11.2004 
35 
Ch. 8: Elementary Graph Algorithms 
Đặc tính của tìm kiếm theo chiều sâu 
Định lý 23.9 
	Trong tìm kiếm theo chiều sâu của một đồ thị vô hướng G , mỗi cạnh của G hoặc là một cạnh cây hoặc là một back edge. 
Chứng minh 
Xét một cạnh bất kỳ ( u , v ) của G . Giả sử d [ u ] < d [ v ]. 
v phải được hoàn tất trước u vì v nằm trong danh sách các đỉnh kề của u . 
Hai trường hợp: 
Cạnh ( u , v ) được thăm dò lần đầu theo hướng từ u đến v : ( u , v ) là cạnh cây. 
Cạnh ( u , v ) được thăm dò lần đầu theo hướng từ v đến u : ( u , v ) là back edge vì đỉnh u còn là xám ( u hoàn tất sau v ). 
7.11.2004 
36 
Ch. 8: Elementary Graph Algorithms 
Các tính chất của tìm kiếm theo chiều sâu 
3/6 
2/9 
1/10 
4/5 
7/8 
12/13 
w 
v 
x 
(a) 
11/16 
14/15 
u 
z 
s 
y 
t 
B 
F 
C 
B 
C 
C 
C 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 
s 
z 
y 
x 
t 
w 
u 
w 
(b) 
7.11.2004 
37 
Ch. 8: Elementary Graph Algorithms 
Ứng dụng của DFS: sắp thứ tự tô pô 
Cho một đồ thị có hướng không có chu trình (directed acyclic graph, hay dag ) G = ( V, E ). Một sắp thứ tự tôpo â của dag G là một sắp xếp tuyến tính của tất cả các đỉnh của G sao cho 
nếu G chứa một cạnh ( u , v ) thì u xuất hiện trước v trong sắp xếp. 
Nhận xét 
Nếu một đồ thị có hướng có chu trình thì không sắp thứ tự tô pô cho nó được. 
7.11.2004 
38 
Ch. 8: Elementary Graph Algorithms 
Sắp thứ tự tô pô 
Cho một dag G = ( V , E ). 
T OPOLOGICAL -S ORT ( G ) 
1	gọi DFS( G ) để tính thời điểm hoàn tất f [ v ] cho mọi đỉnh v 
2	mỗi khi một đỉnh hoàn tất, chèn nó vào phía trước một danh sách 
	liên kết 
3	 return danh sách liên kết các đỉnh 
Thời gian chạy của T OPOLOGICAL -S ORT là ( V + E ). 
7.11.2004 
39 
Ch. 8: Elementary Graph Algorithms 
Sắp thứ tự tô pô -- Ví dụ 
quần lót 
vớ 
quần dài 
giày 
dây lưng 
áo sơ mi 
cà vạt 
áo ngoài 
đồng hồ 
vớ 
quần lót 
quần dài 
giày 
đồng hồ 
áo sơ mi 
dây lưng 
cà vạt 
áo ngoài 
17/18 
11/16 
12/15 
13/14 
9/10 
1/8 
6/7 
2/5 
3/4 
11/16 
12/15 
6/7 
17/18 
9/10 
13/14 
1/8 
2/5 
3/4 
(a) 
(b) 
7.11.2004 
40 
Ch. 8: Elementary Graph Algorithms 
Đặc tính của sắp thứ tự tô pô 
Lemma 23.10 
Một đồ thị có hướng G là không có chu trình (acyclic) 
 một tìm kiếm theo chiều sâu của G không cho ra back edge. 
Chứng minh 
 : 
Giả sử tìm kiếm theo chiều sâu của G cho ra back edge ( u , v ), với v là một tổ tiên của u . Có đường đi P trong rừng theo chiều sâu từ v đến u . Như vậy P và back edge ( u , v ) tạo ra một chu trình. 
 : Bài tập! 
u 
v 
P 
7.11.2004 
41 
Ch. 8: Elementary Graph Algorithms 
Đặc tính của sắp thứ tự tô pô 
Định lý 23.11 
T OPOLOGICAL -S ORT ( G ) tìm được một sắp thứ tự tôpô của một đồ thị có hướng không chứa chu trình G . 
Chứng minh 
Chạy DFS lên dag G = ( V , E ) để xác định thời điểm hoàn tất của các đỉnh. 
Cần chứng tỏ: với mọi cặp u , v  V khác nhau, nếu có một cạnh trong G từ u đến v thì f [ v ] < f [ u ]. 
Xét một cạnh bất kỳ ( u , v ) được thăm dò bởi DFS( G ). Khi đó v không là xám (vì nếu như vậy thì v là tổ tiên của u , và do đó ( u , v ) là back edge, mâu thuẩn! dùng Lemma 23.10). Vậy v là trắng hoặc đen: 
nếu trắng: v trở thành con cháu của u , do đó f [ v ] < f [ u ] 
nếu đen: dỉ nhiên là f [ v ] < f [ u ]. 
7.11.2004 
42 
Ch. 8: Elementary Graph Algorithms