Tại sao độ phức tạp của thuật toán DFS là O(V+E)?
Tại sao độ phức tạp của thuật toán DFS là O(V+E)?
Mỗi đỉnh được thăm đúng một lần và mỗi cạnh được xét đúng một lần (có hướng) hoặc hai lần (vô hướng: từ hai đầu mút).
deg(u); tổng Σ deg(u) = E (có hướng) hoặc 2E (vô hướng).Đăng nhập để tham gia thảo luận cùng mọi người.
Chưa có bình luận nào
Hãy là người đầu tiên chia sẻ suy nghĩ của bạn.