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

Chia sẻ: Nguyen Kien | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST

Báo xấu

106
lượt xem 21
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Trong tài liệu này các bạn sẽ gặp lại cách thể hiện dữ liệu qua đồ thị và thêm một phần quan trọng nữa là các bạn sẽ được tham khảo một số phương pháp duyệt đồ thị rất hiệu quả và cũng rất quan trọng trong ứng dụng

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Phần tích thiết kế giải thuật (phần 10)

Caùc phöông phaùp duyeät ñoà thò Caùc phöông phaùp duyeät ñoà thò Duyeät theo chieàu saâu (Depth-First Search) Duye Duyeät theo chieàu roäng (Breadth-First Search) Duye ng 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 2 1
Depth-First Search (DFS) Khaùi nieäm DFS treân moät ñoà thò voâ höôùng cuõng gioáng nhö DFS ng ng khaùm phaù moät meâ cung vôùi moät cuoän chæ vaø moät thuøng sôn ñoû ñeå ñaùnh daáu, traùnh bò laïc. ng nh nh Ta baét ñaàu töø ñænh s, buoäc ñaàu cuoän chæ vaøo s vaø Ta ñaùnh daáu ñænh naøy laø “ñaõ thaêm”. Sau ñoù ta nh ñaùnh daáu s laø ñænh hieän haønh u. nh nh 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 4 2
Khaùi nieäm Baây giôø, ta ñi theo caïnh (u, v) baát kyø. Baâ nh Neáu caïnh (u, v) daãn chuùng ta ñeán ñænh “ñaõ Ne nh ng thaêm” v, ta quay trôû veà u. Neáu ñænh v laø ñænh môùi, ta di chuyeån ñeán v vaø Ne khoâng queân laêm cuoän chæ cuûa mình theo. Ñaùnh nh daáu ñænh v laø “ñaõ thaêm”. Ñaët v thaønh ñænh hieän nh haønh vaø laëp laïi caùc böôùc tröôùc. nh 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 5 Khaùi nieäm Cuoái cuøng, ta coù theå ñi ñeán moät ñieåm maø taïi ñoù Cuo ng taát caû caùc caïnh keà vôùi noù ñeàu daãn chuùng ta ñeán nh ng caùc ñænh “ñaõ thaêm”. Khi ñoù, ta seõ quay lui baèng ng caùch cuoän ngöôïc cuoän chæ vaø quay laïi cho ñeán ch khi trôû laïi moät ñænh keà vôùi moät caïnh coøn chöa nh ñöôïc khaùm phaù. Laïi tieáp tuïc qui trình khaùm phaù nhö treân. Khi chuùng ta trôû veà s vaø khoâng coøn caïnh naøo keà Khi ng nh vôùi noù chöa bò khaùm phaù laø luùc DFS döøng.ng 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 6 3
Thuaät toaùn Depth-First Search Algorithm DFS(v); Algorithm DFS(v); Input:Moät ñænh v cuûa ñoà thò Input:Moät ñænh v cuû ñoà thò Moä ñænh cuûa Output:Moät caùch gaùn nhaõn cho caùc caïnh ñaõ Output:Moät caù Moä caùch gaù nhaõn cho caù caï gaùn caùc caïnh ñaõ “ñöôïc khaùm phaù” hoaëc “backedge” “ñöôïc khaùm phaù” hoaëc backedge” ñöô khaù phaù hoaë “backedge” for (moïi caïnh e keà vôùi v) do for (moïi caï moï caïnh e keà vôù v) do keà vôùi if caïnh e chöa ñöôïc khaùm phaù then caï chö ñöô khaù phaù then if caïnh e chöa ñöôïc khaùm phaù Goïi w laø ñænh khaùc cuûa e Goï w laø ñænh khaù cuû e Goïi laø ñænh khaùc cuûa if ñænh w laø ñænh môùi then ñænh w laø ñænh môù then if ñænh laø ñænh môùi Gaùn nhaõn e laø “ñöôïc khaùm phaù” Gaù nhaõn e laø “ñöôïc khaù phaù laø ñöô khaùm phaù” Gaùn Goïi ñeä qui DFS(w) Goï ñeä qui DFS(w) Goïi DFS(w) else else Gaùn nhaõn e laø “backedge” Gaù nhaõn e laø “backedge” laø backedge” Gaùn 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 7 Thuaät toaùn Depth-First Search 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 8 4
Xaùc ñònh ñænh keà trong DFS Keát quaû cuûa DFS phuï thuoäc vaøo caùch ta choïn Ke ch ñænh keá tieáp. 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 9 Xaùc ñònh ñænh keà trong DFS Neáu ta baét ñaàu taïi A vaø thöû caïnh noái ñeán F, sau Ne nh ñoù ñeán B, roài ñeán E, C, cuoái cuøng laø G ta ñöôïc: ng ta 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 10 5
Xaùc ñònh ñænh keà trong DFS Neáu cuõng baét ñaàu töø A nhöng ñi theo trình töï: Ne taäp caùc caïnh ñaõ thaêm, backedge vaø caùc ñieåm ñeä nh qui seõ khaùc tröôùc. (Haõy töï laøm vaø kieåm chöùng). ng 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 11 Thuaät toaùn Depth-First Search Baây giôø ta seõ xeùt töøng böôùc cuûa DFS qua ví duï Baâ ng treân: 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 12 6
Thuaät toaùn Depth-First Search 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 13 Thuaät toaùn Depth-First Search 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 14 7
Thuaät toaùn Depth-First Search 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 15 Thuaät toaùn Depth-First Search 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 16 8
Thuaät toaùn Depth-First Search 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 17 Thuaät toaùn Depth-First Search 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 18 9
Thuaät toaùn Depth-First Search 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 19 Thuaät toaùn Depth-First Search 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 20 10