Depth-First Search (DFS)

Chia sẻ: Le Xuan Lê Xuân | Ngày: | Loại File: PDF | Số trang:23

0
313
lượt xem
84
download

Depth-First Search (DFS)

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

DFS trên một đồ thị vô hướng cũng giống như khá phá một mê cung với một cuộn chỉ và một thùng sơn đỏ để đánh dấu, tránh bị lạc.

Chủ đề:
Lưu

Nội dung Text: Depth-First Search (DFS)

  1. 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ät theo chieàu roäng (Breadth-First Search) ng Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Nha Ca tru Dö lie va Gia thua 2 1
  2. Depth-First Search (DFS) Khaùi nieäm DFS treân moät ñoà thò voâ höôùng cuõng gioáng nhö 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ø ñ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 Nha Ca tru Dö lie va Gia thua 4 2
  3. Khaùi nieäm Baây giôø, ta ñi theo caïnh (u, v) baát kyø. nh Neáu caïnh (u, v) daãn chuùng ta ñeán ñænh “ñaõ 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ø 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 Nha Ca tru Dö lie va Gia thua 5 Khaùi nieäm Cuoái cuøng, ta coù theå ñi ñeán moät ñieåm maø taïi ñoù 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à 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 Nha Ca tru Dö lie va Gia thua 6 3
  4. Thuaät toaùn Depth-First Search Algorithm DFS(v); Algorithm DFS(v); Input:Moät ñænh v cuûa ñoà thò Input:Moä ñænh v cuû ñoà thò Input:Moät ñænh cuûa Output:Moät caùch gaùn nhaõn cho caùc caïnh ñaõ Output:Moä caù Output:Moät caùch gaù nhaõn cho caù caï gaùn caùc caïnh ñaõ “ñöôïc khaùm phaù” hoaëc “backedge” “ñöôïc khaù phaù hoaë “backedge” ñöô khaùm phaù” hoaëc 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ù Gaùn laø ñöô khaùm phaù” Goïi ñeä qui DFS(w) Goï ñeä qui DFS(w) Goïi else else Gaùn nhaõn e laø “backedge” Gaù nhaõn e laø “backedge” Gaùn laø backedge” Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Nha Ca tru Dö lie va Gia thua 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 Nha Ca tru Dö lie va Gia thua 8 4
  5. Xaùc ñònh ñænh keà trong DFS Keát quaû cuûa DFS phuï thuoäc vaøo caùch ta choïn 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 Nha Ca tru Dö lie va Gia thua 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 nh ñoù ñeán B, roài ñeán E, C, cuoái cuøng laø G ta ñöôïc: ng Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Nha Ca tru Dö lie va Gia thua 10 5
  6. Xaùc ñònh ñænh keà trong DFS Neáu cuõng baét ñaàu töø A nhöng ñi theo trình töï: 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 Nha Ca tru Dö lie va Gia thua 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ï ng treân: Döông Anh Ñöùc – Nhaääp moân Caááu truùùc Döõ lieääu vaøø Giaûûi thuaäät Nha Ca tru Dö lie va Gia thua 12 6
  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 Nha Ca tru Dö lie va Gia thua 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 Nha Ca tru Dö lie va Gia thua 14 7
  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 Nha Ca tru Dö lie va Gia thua 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 Nha Ca tru Dö lie va Gia thua 16 8
  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 Nha Ca tru Dö lie va Gia thua 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 Nha Ca tru Dö lie va Gia thua 18 9
  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 Nha Ca tru Dö lie va Gia thua 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 Nha Ca tru Dö lie va Gia thua 20 10
  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 Nha Ca tru Dö lie va Gia thua 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 Nha Ca tru Dö lie va Gia thua 22 11
  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 Nha Ca tru Dö lie va Gia thua 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 Nha Ca tru Dö lie va Gia thua 24 12
  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 Nha Ca tru Dö lie va Gia thua 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 Nha Ca tru Dö lie va Gia thua 26 13
  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 Nha Ca tru Dö lie va Gia thua 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 Nha Ca tru Dö lie va Gia thua 28 14
  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 Nha Ca tru Dö lie va Gia thua 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 Nha Ca tru Dö lie va Gia thua 30 15
  16. 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 Nha Ca tru Dö lie va Gia thua 31 Thuaät toaùn Depth-First Search Meänh ñeà: Goïi G laø moät ñoà thò voâ höôùng, treân 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 Nha Ca tru Dö lie va Gia thua 32 16
  17. Thuaät toaùn Depth-First Search Chöùng minh: ng Khaúng ñònh 1. laø hieån nhieân vì DSF duyeät qua 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 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 Nha Ca tru Dö lie va Gia thua 33 Ñoä phöùc taïp thuaät toaùn Haõy nhôù raèng: ng DFS ñöôïc goïi ñuùng 1 laàn öùng vôùi moãi ñænh. ng ng Moãi caïnh ñöôïc xem xeùt ñuùng 2 laàn, moãi laàn 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 Nha Ca tru Dö lie va Gia thua 34 17
  18. Ñ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 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 Ba ng ca ch ca ñænh la 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 Nha Ca tru Dö lie va Gia thua 35 Breadth-First Search (BFS ) 18
  19. Khaùi nieäm Cuõng gioáng nhö DFS, Breadth-First Search 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 Nha Ca tru Dö lie va Gia thua 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 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 Nha Ca tru Dö lie va Gia thua 38 19
  20. 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 ñöôï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 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 Nha Ca tru Dö lie va Gia thua 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 Nha Ca tru Dö lie va Gia thua 40 20
Đồng bộ tài khoản