tailieunhanh - Bài giảng Lý thuyết đồ thị: Chương 3 - TS. Lê Nhật Duy

Bài giảng Lý thuyết đồ thị: Chương 3 Tìm kiếm trên đồ thị, được biên soạn gồm các nội dung chính sau: Duyệt đồ thị theo chiều sâu; Duyệt đồ thị theo chiều rộng; Tìm đường đi; Kiểm tra tính liên thông. Mời các bạn cùng tham khảo! | Chương 3 Tìm kiếm trên đồ thị Nội dung I. Duyệt đồ thị theo chiều sâu II. Duyệt đồ thị theo chiều rộng III. Tìm đường đi IV. Kiểm tra tính liên thông Chương 3 Tìm kiếm trên đồ thị 2 Lý thuyết đồ thị I. Duyệt đồ thị theo chiều sâu Giới thiệu Duyệt đồ thị là quá trình đi qua tất cả các đỉnh của đồ thị sao cho mỗi đỉnh của nó được viếng thăm đúng một lần. Duyệt theo chiều sâu Depth First Search DFS Duyệt theo chiều rộng Breadth First Search BFS Chương 3 Tìm kiếm trên đồ thị 3 I. Duyệt đồ thị theo chiều sâu Nguyên lý Bắt đầu tìm kiếm từ một đỉnh v nào đó của đồ thị. Sau đó chọn u là một đỉnh tùy ý kề với v với đồ thị có hướng thì u là đỉnh sau v là đỉnh đầu của cung uv Lặp lại quá trình này với u cho đến khi không tìm được đỉnh kề tiếp theo nữa thì trở về đỉnh ngay trước đỉnh mà không thể đi tiếp để tìm qua nhánh khác. Chương 3 Tìm kiếm trên đồ thị 4 I. Duyệt đồ thị theo chiều sâu Thứ tự duyệt dcba gkl h fm e Chương 3 Tìm kiếm trên đồ thị 5 . Cài đặt đệ quy B1 Lấy s là một đỉnh của đồ thị B2 Đặt v s B3 Duyệt đỉnh v B4 Nếu đỉnh kề của v đều được duyệt đặt v đỉnh đã được duyệt trước đỉnh v Nếu v s thì đi đến Bước 6 ngược lại trở lại Bước 3. B5 Chọn u là đỉnh kề chưa được duyệt của v đặt v u trở lại Bước 3 B6 Kết thúc Chương 3 Tìm kiếm trên đồ thị 6 . Cài đặt đệ quy Cài đặt bằng mã giả Khai báo các biến ChuaXet Ke DFS v Duyệt đỉnh v ChuaXet v 0 Đánh dấu đã xét đỉnh v for u Ke v if ChuaXet u DFS u void main Nhập đồ thị tạo mảng Ke for v V ChuaXet v 1 Khởi tạo cờ cho đỉnh for v V if ChuaXet v DFS v Chương 3 Tìm kiếm trên đồ thị 7 . Cài đặt không đệ quy Thuật toán B1 Lấy s là một đỉnh của đồ thị B2 Đặt s vào STACK B3 Nếu STACK rỗng đi đến 7. B4 Lấy đỉnh p từ STACK B5 Duyệt đỉnh p B6 Đặt các đỉnh kề của p chưa được xét chưa từng có mặt trong STACK vào STACK trở lại 3. B7 Kết thúc. Chương 3 Tìm kiếm trên đồ thị 8 đồ thị theo chiều sâu Ý nghĩa Kiểm tra đường đi giữa 2 đỉnh Chia đồ thị thành các thành phần liên thông Xây dựng cây khung của đồ thị Kiểm tra xem .