Độ phức tạp thời gian và không gian

Độ phức tạp thời gian:

• O(V + E)
  • Mỗi đỉnh được thêm vào hàng đợi và lấy ra khỏi hàng đợi một lần, và mỗi cạnh được xét một số lần cố định.

Độ phức tạp không gian:

• O(V + E)
  • Danh sách kề lưu mọi cạnh, còn hàng đợi và mảng đã thăm chứa tối đa V đỉnh.

Tóm tắt:

• BFS khám phá các đỉnh theo từng lớp bằng hàng đợi, thăm các đỉnh gần trước rồi đến các đỉnh xa hơn.
• Thứ tự theo lớp này khiến BFS trở thành thuật toán được ưu tiên để tìm đường đi ngắn nhất trong đồ thị không trọng số.