tailieunhanh - Bài giảng Lý thuyết đồ thị: Chương 2 - Ngô Hữu Phúc

"Bài giảng Lý thuyết đồ thị - Chương 2: Các thuật toán tìm kiếm trên đồ thị" thông tin đến các bạn những kiến thức về duyệt đồ thị theo chiều sâu, duyệt đồ thị theo chiều rộng, tìm đường đi và kiểm tra tính liên thông. | CHƯƠNG II CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ 1. Duyệt đồ thị theo chiều sâu DFS-Depth First Search Ý tưởng - Từ đỉnh v1 nào đó chưa thăm thăm v1 rồi tìm đỉnh v2 chưa thăm kề với v1 thăm v2 Thuật toán lặp lại việc thăm cho tới khi tất cả các đỉnh đều được thăm. - Nếu tại một đỉnh vi nào đó không còn đỉnh nào kề với vi là chưa thăm thì quay trở lại tiếp tục tìm đỉnh kề chưa thăm khác của vi-1. 39 CHƯƠNG II CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ đồ thị theo chiều sâu DFS-Depth First Search Procedure DFS v tim kiem theo chieu sau bat dau tu dinh v cac bien Chuaxet Ke la bien toan cuc Begin Tham_dinh v Chuaxet v false For u Є Ke v do If Chuaxet u then DFS u End dinh v da duyet xong Khi đó tìm kiếm theo chiều sâu trên đồ thị được thực hiện nhờ thuật toán sau Begin Khoi tao tat ca cac dinh cua do thi for v Є V do Chuaxet v true for v Є V do If Chuaxet v then DFS v End. 40 CHƯƠNG II CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ đồ thị theo chiều sâu DFS-Depth First Search Ví dụ 1. Xét đồ thị cho trong hình gồm 13 đỉnh các đỉnh được đánh số từ 1 đến 13 như sau 41 CHƯƠNG II CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ 2. Duyệt đồ thị theo chiều rộng BFS- Breadth First Search Ý tưởng -Từ đỉnh v nào đó chưa thăm thăm v cất tất cả các đỉnh u chưa thăm kề với v vào hàng đợi. Lấy từ hàng đợi một đỉnh u thăm u rồi lại cất tất cả các đỉnh t chưa thăm kề với u vào hàng đợi Thuật toán lặp lại việc thăm cho tới khi hàng đợi rỗng. - Nếu tại một đỉnh x nào đó không còn đỉnh nào kề với x là chưa thăm thì quay trở lại tiếp tục tìm đỉnh kề chưa thăm khác của y y là đỉnh trước khi đến x . 42 CHƯƠNG II CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ 2. Duyệt đồ thị theo chiều rộng BFS-Breadth First Search Procedure BFS v BFS bat dau tu dinh v cac bien Chuaxet Ke la bien cuc bo Begin QUEUE Ø QUEUE v ket qua nap vao QUEUE Chuaxet v false While QUEUE Ø do Begin p QUEUE lay p tu QUEUE Tham_dinh p For u Є Ke v do If Chuaxet u then Begin QUEUE u Chuaxet u false End End End Khi đó tìm kiếm theo chiều rộng trên đồ