Thuật toán BFS – Tìm kiếm theo chiều rộng

Thuật toán BFS – Tìm kiếm theo chiều rộng

1. Mô tả
- Đây là thuật toán tìm các đỉnh bằng cách duyệt theo chiều rộng.
- Xuất phát từ 1 đỉnh và đi tới các đỉnh kề nó, tiếp tục cho đến khi không còn đỉnh nào có thể đi.
- Trong quá trình đi đến đỉnh kề, tiến hành lưu lại đỉnh cha của đỉnh kề để khi đi ngược lại từ đỉnh Kết thúc đến đỉnh Xuất phát, ta có được đường đi ngắn nhất.
- Sở dĩ thuật toán này tìm được đường đi ngắn nhất là nhờ vào cơ chế tô màu và lưu đỉnh cha. Quá trình tô màu khiến 1 đỉnh không thể xét 2 lần trở lên và có thể xem được đường đi từ đỉnh Kết Thúc đến đỉnh Xuất phát dựa vào việc lưu đỉnh cha.
- Sau đây là minh họa về thuật toán:
Hình 1 : Xuất phát từ đỉnh 1Untitled
Hình 1
 + Hình 2 : Đi đến đỉnh 2, như vậy nút 1 là nút cha của nút 2
Untitled
Hình 2
 + Hình 3 : Đã đi hết tất cả các đỉnh kề của đỉnh 1, tiến hành bôi đen đỉnh 1
Untitled
Hình 3
 + Hình 4: Xuất phát từ đỉnh 2, chọn đỉnh 3, nút cha của đỉnh 3 là đỉnh 2
Untitled
Hình 4
 + Hình 5 : Xuất phát từ đỉnh 2, bôi đen đỉnh 4, nút cha của đỉnh 4 là đỉnh 2
Untitled
Hình 5
 + Hình 6 : Đã đi hết tất cả các đỉnh kề của đỉnh 2, tiến hành bôi đen đỉnh 2
Untitled
Hình 6
 + Hình 7 : Xuất phát tử đỉnh 3, đi đến đỉnh 7, như vậy đỉnh 3 là đỉnh cha của đỉnh 7
Untitled
Hình 7
 + Hình 8 : Xuất phát từ đỉnh 3, đi đến đỉnh 5, như vậy đỉnh 3 là đỉnh cha của đỉnh 5
Untitled
Hình 8
 + Hình 3 : Đã đi hết tất cả các đỉnh kề của đỉnh 3, tiến hành bôi đen đỉnh 3
Untitled
Hình 9
 + Hình 10 : Xuất phát từ đỉnh 5, đi đến đỉnh 6, như vậy đỉnh 5 là đỉnh cha của đỉnh 6
Untitled
Hình 10
 + Hình 11: Đã đi hết tất cả các đỉnh kề của đỉnh 5, tiến hành bôi đen đỉnh 5
Untitled
Hình 11
 + Hình 12: Đã đi hết tất cả các đỉnh kề của đỉnh 7, tiến hành bôi đen đỉnh 7
Untitled
Hình 12
 + Hình 13 : Đã đi hết tất cả các đỉnh kề của đỉnh6, tiến hành bôi đen đỉnh 6
Untitled
Hình 13
 - Như vậy ta vừa đi hết tất cả các đỉnh trong đồ thị, và mỗi lần đi đến đỉnh mới, ta đều lưu lại nút cha của đỉnh mới, dựa vào những đỉnh cha này, ta có liệt kê đường đi ngắn nhất bằng cách đi ngược từ đỉnh Kết thúc, đến đỉnh cha của đỉnh Kết thúc … rồi đến đỉnh cha của đỉnh tiếp theo … đến đỉnh Bắt đầu.
2. Cài đặt
Hình 14: Cài đặt thuật toán BFS
Untitled
Hình 14
 - Hình 15: In đường đi từ đỉnh Xuất phát đến đỉnh Kết thúc
Untitled

Share:

0 Nhận xét

Categories

. . . 1 [English | DVD] Trọn Bộ DVD Effortless English 3 Ajax 1 Andengine 3 Android 41 Android Studio Cài đặt và phím tắt thông dụng 1 API 1 App Android 1 Applicaiton Chat Multi Client 1 ASP.NET 9 Bài tập lập trình C/C++ có lời giải 1 Bài tập thuật toán C/C++ Và Tuyển tập đề thi olympic 2 Bắt đầu Học Lập Trình 4 Blogger 2 C/C++ 16 C# 21 Câu hỏi phỏng vấn Android 1 Cocos2d-JS 3 Cocos2d-x 3 Code game android 3 Công Cụ Lập Trình 13 Công nghệ 3 Cosos2d 1 CSS 1 Cuộc sống 15 Custom Button trong Android 2 Design Patterns 3 DevExpress 1 Đồ Án 1 DOREMON - NOBITA 2 Dự án 1 Ebook Android 1 English 8 Example Custom Android 1 facebook 1 Fedora 2 Freelancer 1 Game Android 4 Game Android AndEngine 1 Giới thiệu về Ajax 1 Hiệu ứng lắc trong android 1 Hướng dẫn cài đặt Mac OS trên VMware 1 Hướng dẫn download tài liệu miễn phí của website tailieu.vn 1 Hướng dẫn lập trình android 11 Hướng dẫn lập trình Windows Phone 3 Hướng đối tượng 2 Internet được khôi phục 1 Internet of Things 1 iOS 33 Java 9 Kiểm thử phần mềm 1 Kinh nghiệm lập trình 17 Kỹ Năng 1 Lập trình Android FPT Software Training 1 Lập Trình Game Đa Nền Tảng 2 Lập trình game mobile 2 Lập trình iOS FPT Software Training 1 Lập trình mạng 2 LẬP TRÌNH VIÊN CHUYÊN NGHIỆP TRÊN THIẾT BỊ DI ĐỘNG 2 Laptop 1 Libgdx 1 LinQ 3 Linux 6 Load CSDL SQL server ASP.NET 1 Lỗi Eclipse Ctr + Space 1 Mạng Xã Hôi 1 máy thật PC 1 Mbook TIN HỌC A 1 Mbook TIN HỌC B 1 mỗi bài 20 câu 1 NGAN-HANG-DE-THI-TRAC-NGHIEM-ASP.NET 1 Nguyên tắc ngón tay cái trong thiết kế ứng dụng cho điện thoại 1 Nhập môn lập trình C 14 Những câu hỏi phỏng vấn "xương" nhất 1 Những điểm mới kỳ thi THPT quốc gia 2015 1 Object C 1 Phần mềm 3 PHP 2 Phương pháp luyện thi TOEIC 1 Python 2 Review Game 1 SEO 4 Share Acc Fshare 1 Share VIP Miễn phí 1 Sinh viên mới tốt nghiệp – viết gì trong CV 1 Socket Android Client to PC Server C# 2 Socket Chat nhiều Client với server C# 2 Source code 4 Source code game C# 1 Source code game iOS 2 T3H-KHTN 7 Tài Liệu Android 7 Tài Liệu C# 4 Tài liệu hướng dẫn lập trình game với cocos2d-x 1 Tài Liệu iOS 7 Tài Liệu IT 3 Tài Liệu Java 2 Tài liệu Lập trình iOS Tiếng Việt đầy đủ TTTH đại học khoa học tự nhiên 1 Tài Liệu PHP 1 TÀI LIỆU THIẾT KẾ SỐ 1 Tài Liệu Windows Phone 1 Tạo Group Mail Google 1 Tạo hiệu ứng trong lập trình iOS 1 Tạo tên CoCaCoLa 1 Thắc mắc C/C++ 3 THẬP PHÂN sang NHỊ PHÂN không sử dụng MẢNG 1 Thiết kế giao diện Android - App Calculation Android Studio 1 Thiết kế giao diện phần mềm 1 Thuật ngữ cơ bản trong lập trình game AndEngine 1 Thuật toán 5 Thuật toán điều phối FCFS 1 Tiếng Anh 2 Tin Tức 1 Toàn bộ tài liệu ĐTVT 5 năm học 1 Tổng hợp những nơi người lái xe hay bị mắc lỗi tại TPHCM 1 Tutorials Android 2 Tuyến cáp quang AAG đã sửa xong 1 Unity 1 Vim 1 Visual Studyo 2013 1 WEB 1 Website nén JS và CSS tốt nhất 1 Websites Developer 2 Windows 10 Technical Preview 1 Windows Phone 5 WPF 1 XAMARIN 1 Xóa project appcompat_v 1