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

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

• O(V + E)
  • Việc tạo danh sách kề duyệt qua mỗi cạnh một lần, còn quá trình duyệt thăm mỗi đỉnh và xem xét từng cạnh 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 mảng đã thăm và ngăn xếp mỗi thứ chứa tối đa V đỉnh.

Tóm tắt:

• DFS đi sâu trước, quay lui khi không còn hàng xóm nào chưa được thăm.
• Thuật toán chạy trong thời gian tuyến tính và là nền tảng của nhiều thuật toán trên đồ thị.