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

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
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 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 ngDöô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 nhDöô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. nhDöô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.ngDöô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 ...