Bài giảng Giải thuật - Chương 8: Giải thuật tìm kiếm trong đồ thị
ª Biểu diễn các đồ thị
ª Hai cách biểu diễn một đồ thị G = (V, E):
– Biểu diễn danh sách kề (adjacency list)
° mảng Adj gồm |V| danh sách, 1 danh sách cho mỗi đỉnh trong V.
° u ? V, Adj[u] chứa tất cả các đỉnh v (hoặc các con trỏ đến chúng) sao cho (u, v) E.
– Nhận xét
° Biểu diễn danh sách kề cần ?(V + E) memory. (Để đơn giản, ký hiệu V và E thay vì |V| và |E|.)
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
File đính kèm:
- bai_giang_giai_thuat_chuong_8_giai_thuat_tim_kiem_trong_do_t.ppt