Đang chuẩn bị liên kết để tải về tài liệu:
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 6.1. 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Ụ 5.1 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 6.2. 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 6.2. 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 6.3. 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Ụ 6.2 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 6.3. 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 6.3. DUYỆT ĐỒ THỊ THEO CHIỀU SÂU tiếp Thuật toán 6.1 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 6.3. DUYỆT ĐỒ THỊ THEO CHIỀU SÂU tiếp Thuật toán 6.1 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