Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Nếu trong thuật toán duyệt đồ thị, cấu trúc danh sách DS được tổ chức theo kiểu hàng đợi (danh sách vào trước - ra trước – FIFO ) thì ta có phương pháp duyệt theo chiều rộng. Trong phương pháp này việc duyệt có tính chất “lan rộng”. Một đỉnh được duyệt xong ngay sau khi ta đã xét hết tất cả các đỉnh kề với nó. Đỉnh được xét càng sớm thì sớm trở thành duyệt xong. | BÀI 12 6.1.3. Duyệt theo chiều rộng Breadth-First Search Nếu trong thuật toán duyệt đồ thị cấu trúc danh sách DS được tổ chức theo kiểu hàng đợi danh sách vào trước - ra trước - FIFO thì ta có phương pháp duyệt theo chiều rộng. Trong phương pháp này việc duyệt có tính chất lan rộng . Một đỉnh được duyệt xong ngay sau khi ta đã xét hết tất cả các đỉnh kề với nó. Đỉnh được xét càng sớm thì sớm trở thành duyệt xong. Thuật toán 6.3 Duyệt đồ thị theo chiều rộng 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. 1 procedure D_RONG v 2 begin 3 Q 0 4 enqueue v into Q Nạp v vào cuối hàng đợi Q 5 Duyet v true 6 while Q 0 do 7 begin 8 dequeue z from Q Loại z ra khỏi đầu hàng đợi Q 9 Thăm_đỉnh z 10 for u G DK z do 11 if Duyet u then 12 begin 13 enqueue u into Q 14 Duyet u true 15 16 e 17 end end end 18 BEGIN Chương trình chính 19 20 21 for v G V do Duyet v false for v G V do if Duyet v then D_RONG v 22 END . Thuật toán này cũng có độ phức tạp là O n m Ví dụ 6.2 Đồ thị trong Ví dụ 6.1 được duyệt theo chiều rộng. Hình 6.2. Thứ tự của các đỉnh được duyệt theo chiều rộng 6.2. Một số ứng dụng của thuật toán duyệt đồ thị 6.2.1. Bài toán tìm đường đi Giả sử a và b là hai đỉnh nào đó của đồ thị vô hướng G. Hãy tìm đường đi nếu có từ đỉnh a đến đỉnh b. Bài toán này đã được giải quyết bằng Thuật toán 1.4 hoặc thuật toán Warshall. Theo các phương pháp duyệt đồ thị các lời gọi thủ tục D_SAU a hoặc D_RONG a cho phép thăm tất cả các đỉnh thuộc cùng thành phần liên thông với đỉnh a. Vì vậy sau khi thực hiện xong thủ tục nếu Duyet b false thì không có đường đi từ đỉnh a đên đỉnh b ngược lại thì đỉnh b thuộc cùng mảng liên thông với đỉnh a hay nói một cách khác có đường đi từ a đến b. Để khôi phục đường đi ta dùng thêm một biến mảng Truoc. Thành phần Truoc u ghi lại đỉnh đến trước đỉnh u trên đường duyệt từ a tới u. Khi đó trong thủ tục D_SAU v cần sửa đổi câu lệnh if ở dòng lệnh 6 như sau 6 if Duyet u then begin Truoc u V D_SAU u end còn
