廣度優先搜索完整圖的複雜度是多少？

BFS的複雜度被認爲是線性的，即O（V + E），但是有向完整圖中邊的總數是V *（V-1），它是圖形。那麼BFS會花費O（V^2）時間遍歷完整的圖表嗎？廣度優先搜索完整圖的複雜度是多少？

查看答案。抱歉的不便。我沒有看到algirthm是BFS。檢查我的答案。 – coderredoc

是的，我假設你已經做了數學。

O(V+E) = O(V + V*(V-1)) 
     = O(V + V*V - V) 
     = O(V*V)

2017-08-25 02:50:31

給出這個結果，我們可以得出結論：使用鄰接表的最壞情況BFS不是線性的，而是二次的？ –

@UttakarshTikku它在算法的輸入大小上是線性的，這是頂點數量的二次方。 –

非常感謝！這非常有幫助！ –

BFS運行在O(V + E)時間提供的圖表由鄰接表結構表示。

在密集的情況下，你會看到答案將是O(V+E)。（表示是鄰接表）。

在鄰接矩陣的情況下O(V^2)。

無論圖表如何，您總是會先覆蓋起點的鄰居。然後再爲鄰居重複這個。所以你可以看到它總是需要遍歷O(V+E)時間，但這是表示使鄰接矩陣變得困難。所以它將是O(V^2) 。

_{這是因爲我們希望找到每一次什麼是相鄰的給定的頂點「U」，我們遍歷整個數組adjmatrix[u]，這是長度的邊緣| V |}

2017-08-25 02:41:33 coderredoc

我在這裏得到的是這裏的頂點數和邊數的關係。完整圖中的邊數是頂點數的函數，對於完整的有向圖精確爲V *（V-1）。 –

是的，但表示很重要。這就是我所說的。 – coderredoc

回答