tailieunhanh - Bài giảng Lý thuyết đồ thị: Chương 6 - PGS.TS. Hoàng Chí Thành

Bài giảng Lý thuyết đồ thị: Chương 6 Các thuật toán duyệt đồ thị, cung cấp cho người đọc những kiến thức như: Các thuật toán duyệt đồ thị; Một số ứng dụng của các thuật toán duyệt đồ thị. Mời các bạn cùng tham khảo! | CHƯƠNG 6 CÁC THUẬT TOÁN DUYỆT ĐỒ THỊ 1 NỘI DUNG Các thuật toán duyệt đồ thị Một số ứng dụng của các thuật toán duyệt đồ thị 2 . CÁC PHÉP DUYỆT ĐỒ THỊ Khái niệm duyệt đồ thị Thuật toán duyệt đồ thị Duyệt đồ thị theo chiều sâu Duyệt đồ thị theo chiều rộng 3 KHÁI NIỆM DUYỆT ĐỒ THỊ Duyệt đồ thị là một cách liệt kê tất cả các đỉnh của đồ thị thành một danh sách tuyến tính. - Cho một cách đi qua tất cả các đỉnh của đồ thị để truy nhập thêm bớt thông tin - Duyệt đồ thị không phụ thuộc vào hướng của cạnh. 4 VÍ DỤ 3 2 D 4 B H 1 5 A E 8 G 6 C 7 F Thứ tự duyệt A B D H E G F C 5 . THUẬT TOÁN DUYỆT ĐỒ THỊ Cho đồ thị G V E với x0 là một đỉnh của G. Dùng một cấu trúc dữ liệu kiểu danh sách kí hiệu là DS để chứa các đỉnh. 6 . THUẬT TOÁN DUYỆT ĐỒ THỊ tiếp Thuật toán 1 Khởi đầu DS x0 2 Lấy đỉnh x ra khỏi đầu DS 3 Duyệt đỉnh x 4 Nạp các đỉnh của F x vào DS 5 Nếu DS thì quay lên bước 2 6 Dừng. 7 . DUYỆT ĐỒ THỊ THEO CHIỀU SÂU Danh sách DS được tổ chức theo kiểu stack danh sách vào sau ra trước LIFO . Mỗi lần duyệt một đỉnh ta duyệt đến tận cùng mỗi nhánh rồi mới chuyển sang duyệt nhánh khác. 8 VÍ DỤ Thứ tự duyệt của các đỉnh trên đồ thị 13 14 6 8 2 12 1 3 11 5 9 7 4 10 15 9 . DUYỆT ĐỒ THỊ THEO CHIỀU SÂU tiếp 1. Bắt đầu duyệt từ một đỉnh x0 nào đó của đồ thị. 2. Chọn x là đỉnh kề nào đó của x0 và lặp lại quá trình duyệt đối với đỉnh x. Giả sử đang xét đỉnh x. - Nếu tìm được đỉnh y chưa được duyệt thì xét đỉnh này và bắt đầu từ đó tiếp tục quá trình duyệt - Nếu không còn đỉnh kề với x chưa được duyệt thì nói rằng đỉnh x đã duyệt xong quay trở lại tiếp tục duyệt từ đỉnh mà từ đó đến được đỉnh x - Nếu quay trở lại đúng đỉnh x0 thì phép duyệt kết thúc 10 . DUYỆT ĐỒ THỊ THEO CHIỀU SÂU tiếp Thuật toán Depth-First Search Dữ liệu Biểu diễn mảng DK các danh sách kề của đồ thị vô hướng G. Kết quả Danh sách các đỉnh của đồ thị G. 11 . DUYỆT ĐỒ THỊ THEO CHIỀU SÂU tiếp Thuật toán 1 procedure D_SAU v 2 begin 3 Thăm_đỉnh v 4 Duyet v true 5 for u DK v do 6 if Duyet