Các phương pháp duyệt đồ thị

Chia sẻ: Trần Huy | Ngày: | Loại File: PDF | Số trang:23

Thêm vào BST

Báo xấu

94
lượt xem 12
download

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

DFS trên một đồ thị vô hướng cùng giống như khám phá một mê cung với một cuộn chỉ và một thùng sơn đỏ để đánh dấu, tránh bị lạc. Ta bắt đầu từ đỉnh S, buộc đầu cuộn chỉ vào S và đánh dấu đỉnh này là " đã thăm". Sau đó ta đánh dấu s là đỉnh hiện hành u.

Chủ đề:

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

Lưu

Nội dung Text: Các phương pháp duyệt đồ thị

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
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 21 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 22 11
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 23 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 24 12
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 25 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 26 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 27 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 28 14
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 29 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 30 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 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 thaønh phaàn lieân thoâng neân caây naøy laø caây toái nh ñaïi. 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 33 Ñoä phöùc taïp thuaät toaùn Haõy nhôù raèng: Haõ ng DFS ñöôïc goïi ñuùng 1 laàn öùng vôùi moãi ñænh. DFS ng ng Moãi caïnh ñöôïc xem xeùt ñuùng 2 laàn, moãi laàn Moã nh ng töø moät ñænh keà vôùi noù 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 34 17
Ñoä phöùc taïp thuaät toaùn Vôùi nS ñænh vaø mS caïnh thuoäc thaønh phaàn lieân Vô nh nh thoâng chöùa s, moät pheùp DFS baét ñaàu taïi s seõ chay vôùi thôøi gian O(nS + mS ) neáu: Ñoà thò ñöôïc bieååu dieãn baèèng CTDL daïïng danh saùùch ñöô bie ba ng da ng sa ch keàà. ke Ñaët nhaõn cho moäät ñænh laøø “ñaõ thaêm” vaøø kieååm tra mo ñænh la va kie xem moäät ñænh “ñaõ thaêm” chöa toáán chi phí mo ñænh chö to phí O(degree). Baèèng caùùch ñaët nhaõn cho caùùc ñænh laøø “ñaõ thaêm”, ta ca ñænh la Ba ng ca ch coùù theåå xem xeùùt moäät caùùch heää thoâng caùùc caïïnh keàà vôùùi co the xe mo ca ch he ca ca nh ke vô ñænh hieään haøønh neân ta seõ khoâng xem xeùùt moäät caïïnh ñænh hie ha nh xe mo ca nh quaùù 1 laààn. qua la 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 35 Breadth-First Search Breadth (BFS ) 18
Khaùi nieäm Cuõng gioáng nhö DFS, Breadth-First Search Cuõ ng (BFS) duyeät qua toaøn boä caùc ñænh thuoäc moät thaønh phaân lieân thoâng cuûa ñoà thò vaø xaùc ñònh nh ñöôïc moät caây toái ñaïi cuûa noù vôùi moät soá thuoäc tính höõu ích: 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 37 Khaùi nieäm Ñænh xuaát phaùt s ôû möùc 0, vaø cuõng nhö trong Ñæ DFS, ñöôïc xem nhö moät ñieåm moác trong quaù trình tìm kieám. ÔÛ löôït thöù nhaát, cuoän chæ ñöôïc môû ra doïc theo chieàu daøi moät caïnh, vaø taát caû caùc ñænh keà vôùi nh ñieåm moác (caùch ñieåm moác ñuùng moät caïnh) ñeàu ch ng nh ñöôïc thaêm. Caùc ñænh naøy ñöôïc ñaët ôû möùc 1 (caùc caïnh töông Ca nh öùng cuõng vaäy) 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 38 19
Khaùi nieäm ÔÛ löôït thöù hai, taát caû caùc ñænh môùi caùch moác 2 ch caïnh seõ ñöôïc thaêm vaø ñöôïc ñaët ôû möùc 2 nh Qui trình naøy tieáp tuïc cho ñeán khi taát caû caùc ñænh Qui ñöôïc thaêm (ñöôïc gaùn vaøo moät möùc naøo ñoù). ). Nhaõn cuûa moïi ñænh v töông öùng vôùi ñöôøng ñi qua Nhaõ ng ng ít caïnh nhaát (ngaén nhaát) töø s ñeán v. 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 39 Breadth-First Search (BFS ) 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 40 20