Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Bài giảng Lý thuyết đồ thị: Chương 3 - Các thuật toán tìm kiếm trên đồ thị và ứng dụng của Nguyễn Trần Phi Phương sau đây trình bày về tìm kiếm theo chiều sâu trên đồ thị; tìm kiếm theo chiều rộng trên đồ thị; tìm đường đi và kiểm tra tính liên thông. | Chương 3 CÁC THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ VÀ ỨNG DỤNG 3.1 Tìm kiếm theo chiều sâu trên đồ thị Depth First Search B1. Xuất phát từ 1 đỉnh cho trước nào đó. B2. Xử lý đỉnh này và đánh dấu để không xử lý lần sau. B3. Đưa tất cả các đỉnh kề với nó vào danh sách xử lý và chọn 1 đỉnh để xử lý tiếp theo. B4. Quay lại B2 cho đến khi không còn đỉnh trong danh sách. VD _ KA w J 4-Ầ J 1 . r -4-9 1 1 Ầ r 4 y T x A r Băt đầu từ 1. Đưa các đỉnh kề với 1 vào DS 2 4 5 1 Chọn 2 để xử lý. Đưa các đỉnh kề với 2 vào DS 3 4 5 . Thứ tự 1 2 3 5 4 6 Lý thuyết đồ thị 3 17 03 2011 2 3.1 Tìm kiếm theo chiều sâu trên đồ thị Phân tích - Dùng cấu trúc Stack - Sử dụng mảng đánh dấu là mảng 1 chiều int danhdau maxV Quy ước - danhdau i 0 đỉnh i chưa được xét - danhdau i 1 đỉnh i đã được xét 17 03 2011 Lý thuyết đồ thị
