Thuật toán bfs tìm đường đi ngắn nhất năm 2024
Breath First Search (BFS) cùng với Depth First Search là những thuật toán cơ bản dùng để duyệt qua đồ thị. Trong bài viết này, chúng ta sẽ cùng làm rõ ý tưởng cũng như cách hiện thực thuật toán này. Mục lục1. Ý tưởngÝ tưởng cơ bản như sau:
2. Hiện thựcCách hiện thực thuật toán BFS cũng tương tự như DFS ở bài viết Thuật toán Depth First Search. Ta cần dùng một mảng Đầu vào cần một
0. Thực hiện các bước như sau:
Code tham khảo: BreathFirstSearch
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
3. Áp dụngTa trở lại với bài toán trước ở bài viết Thuật toán Depth First Search. Bài toán: Cho đồ thị Về ý tưởng thì tương tự, nhưng sẽ đổi lời giải bằng thuật toán BFS để xem kết quả nhé. Code tham khảo: BreathFirstPaths
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
Thử nghiệm với đồ thị sau đây: Đồ thị 1 Hàm 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 1 để test: DepthFirstPaths
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Kết quả là:
Và đường đi mà thuật toán cho kết quả là: Đường đi cho Đồ thị 1 Có thể thấy, thuật toán BFS luôn cho đường đi ngắn nhất từ đỉnh gốc tới các đỉnh khác trong đồ thị vô hướng không có trọng số. “Ngắn” ở đây là qua ít đỉnh nhất nhé các bạn 😆. 4. Đánh giáThuật toán sẽ duyệt qua tất cả các đỉnh nếu đồ thị liên thông. Giống như DFS, BFS cũng là thuật toán tìm kiếm mù, mang tính chất vét cạn. |