在图遍历n + 2E中，BFS的最坏时间复杂度是多少？ [英] Is the worst time complexity of BFS in a graph traversal n+2E?

问题描述

我知道在图遍历中BFS的时间复杂度是 O（V + E），因为每个顶点和每个边将在最坏的情况下被探索。 p>

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

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

所有顶点的度数之和图形=无边数* 2 = 2E

因此时间复杂度是 n + 2E ..我是否正确？

解决方案

对于随机图，时间复杂度为 O（V + E）：广度优先搜索

如链接所述，根据图的拓扑结构， O（E）可能会从 O（V） code>（如果你的图是非循环的）为 O（V ^ 2）（如果所有的顶点都相互连接）。 b
因此时间复杂度从 O（V + V）= O（V）变化为 O（V + V ^ 2）= O（V ^ 2）根据图的拓扑结构。



此外，自 | V | < = 2 | E | ，那么 O（3E）= O（E）也是正确的，但边界更宽松。


I understand that time complexity of BFS in a graph traversal is O( V + E ) since every vertex and every edge will be explored in the worst case.

Well,is the exact time complexity v+2E ??

Every vertex is explored once+ Every adjacent vertices

The sum of the degree of all the vertices in a graph= No of edges*2= 2E

Thus the time complexity is n+2E..Am i correct?

解决方案

For a random graph, the time complexity is O(V+E): Breadth-first search

As stated in the link, according to the topology of your graph, O(E) may vary from O(V) (if your graph is acyclic) to O(V^2) (if all vertices are connected with each other).

Therefore the time complexity varies fromO(V + V) = O(V) to O(V + V^2) = O(V^2) according to the topology of your graph.

Besides, since |V| <= 2 |E|, then O(3E) = O(E) is also correct, but the bound is looser.

这篇关于在图遍历n + 2E中，BFS的最坏时间复杂度是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！