图遍历中BFS的最差时间复杂度是n + 2E吗？
我了解图遍历中BFS的时间复杂度是O( V + E )因为在最坏的情况下都会探索每个顶点和每个边。
那么，确切的时间复杂度是v+2E吗？
每个顶点浏览一次+每个相邻顶点
一个顶点上所有顶点的度数之和 graph= No of edges*2= 2E
因此，时间复杂度是n+2E..我正确吗？
回答：
对于随机图，时间复杂度为O(V+E)：广度优先搜索
如链接中所述，根据图的拓扑结构，其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)也是正确的，但界限较宽松。
以上是 图遍历中BFS的最差时间复杂度是n + 2E吗？ 的全部内容， 来源链接： utcz.com/qa/423037.html
