tailieunhanh - Cẩm nang thuật toán tập 2 part 4

Tham khảo tài liệu 'cẩm nang thuật toán tập 2 part 4', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | CÁC THUẬT TOAN cơ BÂN VỀ Hồ THỊ 99 00 __00 0Ẽ00ẺẺ0 00 K I lình Nội dung ngăn xếp trong quá trình tìm kiêm Nút được viếng đâu tiên là A các cạnh AF AB AC và AG được duyệt và các đỉnh F B c và G được đạt vào ngăn xếp. Kế đến G được lấy ra chú ý ràng G là nút cuối cùng trong xâu kê của A và các cạnh GA GE được duyệt kết quả là E được đặt vào ngăn xếp A không được đạt vào ngỉin xếp một ĩân nữa . Kế tới EG EF và ED được duyệt và D được đặt vào ngùn xếp. Hìngh minh họa nội dung cùa ngAn xếp trong suốt quá trình tìm kiếm và Hình cho thấy các bước tiếp theo của Hình . Có lẽ độc giả đã nghĩ răng chương trình trên không viếng các cạnh và nút theo thứ tự giông như trường hợp cài đặt đê quy. Như trong Chương 5 điêu nãy có thể thấy được nhờ chú ý vào thứ tự các cạnh được đưa vào ngân xếp trong chương trình trôn chúng ta viếng cạnh trong xâu kê của mỗi nút ngược lại với thứ tự xuất hiện của chúng trong xâu. Nếu chúng ta duyệt xâu theo thứ tự đảo thì thứ tự viếng thăm các nút giống như trong cài đạt đê qui. Giống như Chương 5 lúc đó cây con phâi được đặt vào ngăn xếp trước cây con trái trong cài đặt không đệ qui. Tuy nhiên đối với các đô thị không nhất thiết phải tuân thủ nghiêm ngặt vào thứ tự duyệt cạnh trong cài đặt đệ qui bôi vì như đã thấy nhiêu nhân tố khác cũngành hưởng đốn thứ tự duyệt cạnh. Trong Chương 31 chúng ta sẽ thấy có rất nhiêu lựa chọn cho phép chúng ta lợi dụng khả năng linh động này vào các thuật toán. 100 TÌM KIẾM ƯU TIÊN lìỀ RỘNG Hình lìm kiêin iru liên dụ sâu dựa vào ngàn xếp TÌM KIỂM ƯU TIÊN BỀ RỘNG BREADTH-FIRST Giống như duyệt cây xem Chương 4 chúng ta có thể dùng mộtt hàng đợi thay vi ngăn xếp làm cấu trúc dữ liêu để lưu các đỉnh. Đỉêu hây đưa tới một thuật toán duyệt đô thị cổ điển thứ hai được gọi là tìm kiếm ưu tiên hỉè rông. Để cài đạt thuật toán tìm kiếm này chúng ta can thay đổi các phép toán trên ngăn xếp băng các phép toán trên hàng đợi như sau CÁC THUẬT TOÁN CƠỈÌÀN VỀ Hồ THỊ ỈOỈ procedure listbfs var id k . .