Phần tích thiết kế giải thuật (phần 11)

Tài liệu này sẽ cung cấp cho các bạn sẽ đi từng bước trong kĩ thuật duyệt đồ thị theo chiều sâu DFS, thông qua đó các bạn có thể hình dung được cách cài đặt nó trên máy tính thông quan cơ chế queue, rất đơn giản và nhẹ nhàng
Nội dung trích xuất từ tài liệu:
Phần tích thiết kế giải thuật (phần 11) Thuaät toaùn Depth-First SearchDöông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Ca tru Dö lie va Gia thua Nha 21 Thuaät toaùn Depth-First SearchDöông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Ca tru Dö lie va Gia thua Nha 22 11 Thuaät toaùn Depth-First SearchDöông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Ca tru Dö lie va Gia thua Nha 23 Thuaät toaùn Depth-First SearchDöông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Ca tru Dö lie va Gia thua Nha 24 12 Thuaät toaùn Depth-First SearchDöông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Ca tru Dö lie va Gia thua Nha 25 Thuaät toaùn Depth-First SearchDöông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Ca tru Dö lie va Gia thua Nha 26 13 Thuaät toaùn Depth-First SearchDöông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Ca tru Dö lie va Gia thua Nha 27 Thuaät toaùn Depth-First SearchDöông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Ca tru Dö lie va Gia thua Nha 28 14 Thuaät toaùn Depth-First SearchDöông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Ca tru Dö lie va Gia thua Nha 29 Thuaät toaùn Depth-First SearchDöông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Ca tru Dö lie va Gia thua Nha 30 15 Thuaät toaùn Depth-First SearchDöông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Ca tru Dö lie va Gia thua Nha 31 Thuaät toaùn Depth-First Search Meänh ñeà: Goïi G laø moät ñoà thò voâ höôùng, treân Me nh ng ñoù ta seõ thöïc hieän thao taùc DFS vôùi ñænh baét ñaàu laø s thì: 1. Pheùp duyeät seõ thaêm taát caû caùc ñænh cuøng ng thaønh phaàn lieân thoâng vôùi s. nh 2. Caùc caïnh coù nhaõn “ñaõ thaêm” seõ taïi ra moät nh caây toái ñaïi cuûa thaønh phaàn lieân thoâng chöùa nh s.Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Ca tru Dö lie va Gia thua Nha 32 16 Thuaät toaùn Depth-First Search Chöùng minh: Ch ng Khaúng ñònh 1. laø hieån nhieân vì DSF duyeät qua Kha ng taát caû caùc ñænh keà vôùi ñænh hieän haønh. (Coù theå nh chöùng minh hoaøn chænh hôn baèng phaûn ng ng chöùng). ng Khaúng ñònh 2. ñuùng do ta chæ ñaùnh daáu caùc Kha ng ng nh caïnh ñi ñeán moät ñænh môùi neân khoâng theå taïo nh ra chu trình. Nhö vaäy DFS taïo ra moät caây. Hôn nöõa, DFS thaêm taát caû caùc ñænh thuoäc ...