Tại sao độ phức tạp của BFS O (V + E) thay vì O (V * E)?

Question

Một số giả ở đây (bỏ qua phong cách của tôi)

Bắt đầu từ v1 (enqueued):

function BFS(queue Q) 
    v2 = dequeue Q 
    enqueue all unvisited connected nodes of v2 into Q 
    BFS(Q) 
end // maybe minor problems here 

Vì có V đỉnh trong đồ thị, và những đỉnh V được kết nối với E cạnh, và quý khách đến thăm nhận các nút kết nối (tương đương với các kết nối được truy cập) nằm trong vòng lặp bên trong (vòng lặp bên ngoài là đệ quy chính nó), dường như với tôi rằng độ phức tạp phải là O (V * E) thay vì O (V + E). Bất cứ ai có thể giải thích điều này cho tôi?

Answer 1

E không phải là số cạnh cạnh với mỗi đỉnh - thực tế là tổng số cạnh của biểu đồ. Xác định nó theo cách này là hữu ích bởi vì bạn không nhất thiết phải có cùng số cạnh trên mỗi đỉnh.

Vì mỗi cạnh được truy cập một lần vào lúc DFS kết thúc, bạn nhận được độ phức tạp O (E) từ phần đó. Sau đó, bạn thêm O (V) để truy cập mỗi đỉnh một lần và nhận được O (V + E) trên tổng số.