Cách hoạt động?

BFS duy trì một dấu visited cho mỗi đỉnh và một queue gồm các đỉnh cần xử lý.

Quy trình từng bước:

1. Đánh dấu đỉnh bắt đầu là đã thăm và thêm đỉnh đó vào hàng đợi.
2. Lấy đỉnh ở đầu hàng đợi ra và ghi lại thứ tự thăm.
3. Với mỗi đỉnh kề chưa thăm (theo thứ tự tăng dần), đánh dấu đỉnh đó là đã thăm và thêm vào hàng đợi. Đánh dấu khi thêm vào hàng đợi giúp một đỉnh không bị thêm hai lần.
4. Lặp lại cho đến khi hàng đợi trống.

Ví dụ với các đỉnh từ 0 đến 3 và các cạnh [0,1, 0,2, 1,3, 2,3], bắt đầu tại 0:

• Thăm 0, thêm 1 và 2 vào hàng đợi; thăm 1, thêm 3 vào hàng đợi; thăm 2; thăm 3.
• Thứ tự thăm: [0, 1, 2, 3] (so sánh với DFS: [0, 1, 3, 2]).