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

Trong lý thuyết đồ thị, tìm kiếm theo chiều rộng (BFS) là một thuật toán tìm kiếm trong đồ thị trong đó việc tìm kiếm chỉ bao gồm 2 thao tác: (a) thăm một đỉnh của đồ thị; (b) thêm các đỉnh kề với đỉnh vừa thăm vào danh sách có thể thăm trong tương lai. 

Thuật toán

1. Lấy ra đỉnh đầu tiên trong hàng đợi và thăm nó
   • Nếu đỉnh này chính là đỉnh đích, dừng quá trình tìm kiếm và trả về kết quả.
   • Nếu không phải thì chèn tất cả các đỉnh kề với đỉnh vừa thăm nhưng chưa được thăm trước đó vào hàng đợi.
2. Nếu hàng đợi là rỗng, thì tất cả các đỉnh có thể đến được đều đã được thăm – dừng việc tìm kiếm và trả về "không thấy".
3. Nếu hàng đợi không rỗng thì quay về bước 2.

Bài tập : 

Queue (FIFO first in first out)

Duyệt 1: đưa 2, 3, 4 vào hàng đợi : => 2, 3, 4

duyệt 2: đưa 5, 6 vào hàng đợi =>3, 4, 5, 6

duyệt 3: không sử lý =>4, 5, 6

duyệt 4:đưa 7, 8 vào hàng đợi =>5, 6, 7, 8

duyệt 5: đưa 9, 10 vào hàng đợi => 6, 7, 8, 9, 10

duyệt 6: không sử lý: =>7, 8, 9, 10

duyệt 7: đưa 11, 12 vào hàng  đợi = > 8, 9, 10, 11, 12

duyệt 8: không xử lý:

duyệt 9:---------------

duyệt 10:--------------

duyệt 11:---------------

duyệt 12:----------------------

kết quả:  1, 2,3, 4, 5, 6, 7, 8, 9, 10, 11, 12