algorithm - BFS在一次图遍历中最差的时间复杂度是n+2E吗？

Question

我理解 BFS 在图遍历中的时间复杂度是 O( V + E ) 因为在最坏的情况下每个顶点和每条边都会被探索。

那么，确切的时间复杂度是 v+2E ??

每个顶点探索一次+每个相邻的顶点

图中所有顶点的度数之和= No of edges*2= 2E

因此时间复杂度是n+2E..我说的对吗？

Answer 1

对于一个随机图，时间复杂度是O(V+E) : Breadth-first search

如链接中所述，根据您图表的拓扑结构，O(E)可能不同于 O(V) (如果你的图是非循环的)到 O(V^2) (如果所有顶点都相互连接)。

因此时间复杂度不同于O(V + V) = O(V)至 O(V + V^2) = O(V^2)根据你的图的拓扑结构。

此外，自 |V| <= 2 |E| , 然后 O(3E) = O(E)也是正确的，但界限更宽松。