Chiều rộng Phân tích phức tạp thời gian tìm kiếm đầu tiên

Question

Độ phức tạp thời gian để đi qua từng cạnh liền kề của một đỉnh là O(N), trong đó N là số cạnh kề nhau. Vì vậy, đối với V số đỉnh phức tạp thời gian trở thành O(V*N) = O(E), trong đó E là tổng số cạnh của biểu đồ. Vì việc loại bỏ và thêm một đỉnh từ/vào Hàng đợi là O(1), tại sao nó được thêm vào độ phức tạp tổng thể của BFS là O(V+E).

Answer 1

Tôi hy vọng điều này sẽ hữu ích đối với bất kỳ ai gặp khó khăn trong việc hiểu sự phức tạp về thời gian tính toán cho Breadth First Search a.k.a BFS.

Queue graphTraversal.add(firstVertex); 

// This while loop will run V times, where V is total number of vertices in graph. 
while(graphTraversal.isEmpty == false) 

    currentVertex = graphTraversal.getVertex(); 

    // This while loop will run Eaj times, where Eaj is number of adjacent edges to current vertex. 
    while(currentVertex.hasAdjacentVertices) 
     graphTraversal.add(adjacentVertex); 

    graphTraversal.remove(currentVertex); 

Thời gian phức tạp như sau:

V * (O(1) + Eaj + O(1)) 
V + V * Eaj + V 
2V + E(total number of edges in graph) 
V + E 

tôi đã cố gắng đơn giản hóa mã và độ phức tạp tính toán nhưng vẫn còn nếu bạn có bất kỳ câu hỏi cho tôi biết.

Answer 2

Thực hiện thao tác O(1)L lần, dẫn đến độ phức tạp O(L). Vì vậy, việc loại bỏ và thêm một đỉnh từ/vào Hàng đợi là O (1), nhưng khi bạn làm điều đó cho các đỉnh V, bạn sẽ nhận được độ phức tạp O(V). Do đó, O(V) + O(E) = O(V+E)

Answer 3

Xem xét biểu đồ sau, chúng ta thấy độ phức tạp của thời gian là O (| V | + | E |) nhưng không phải là O (V * E).

danh sách kề

V  E 
v0:{v1,v2} 
v1:{v3} 
v2:{v3} 
v3:{} 

hoạt động như thế nào BFS trình Step by Step

Bước 1:

host ở xa danh sách:

V  E 
v0: {v1,v2} mark, enqueue v0 
v1: {v3} 
v2: {v3} 
v3: {} 

Bước 2:

host ở xa danh sách:

V  E 
v0: {v1,v2} dequeue v0;mark, enqueue v1,v2 
v1: {v3} 
v2: {v3} 
v3: {} 

Bước 3:

danh sách một host

V  E 
v0: {v1,v2} 
v1: {v3} dequeue v1; mark,enqueue v3 
v2: {v3} 
v3: {} 

Step4:

danh sách một host

V  E 
v0: {v1,v2} 
v1: {v3} 
v2: {v3} dequeue v2, check its adjacency list (v3 already marked) 
v3: {} 

Bước 5:

host ở xa danh sách:

V  E 
v0: {v1,v2} 
v1: {v3} 
v2: {v3} 
v3: {} dequeue v3; check its adjacency list 

Bước 6:

danh sách một host

V  E 
v0: {v1,v2} |E0|=2 
v1: {v3} |E1|=1 
v2: {v3} |E2|=1 
v3: {}  |E3|=0 

Tổng số bước sau:

|V| + |E0| + |E1| + |E2| +|E3| == |V|+|E| 
4 + 2 + 1 + 1 + 0 == 4 + 4 
          8 == 8 

Giả sử một đại diện danh sách kề, V là số đỉnh, E số cạnh.

Mỗi đỉnh được hấp thụ và khử nhiễu nhiều nhất một lần.

Quét cho tất cả các đỉnh liền kề mất O (| E |) thời gian, vì tổng độ dài của danh sách kề là | E |.

Do đó Độ phức tạp về thời gian của BFS mang lại một sự phức tạp về thời gian O (| V | + | E |).

Answer 4

I understood the part V+E in the complexity. 
But I have 2 questions 
1). V * Eaj should give 2E? 
(as it is the total no of edges accessed, and each edge is checked twice, by each of it ends) 

2) Also the complexity is V + E 
but in worst case we take E = V*(V-1)/2 
So V isn't required here as we could say we E = V²... 
Can't we say complexity O(E) only?