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);
时间复杂度如下：
V * (O(1) + O(Eaj) + O(1))
V + V * Eaj + V
2V + E(total number of edges in graph)
V + E
你完全正确的是每个节点的平均工作量是O（E / V） . 这意味着，通过E / V的某个倍数，从上面开始完成总工作量 . 如果我们考虑BFS实际在做什么，每个节点完成的工作可能看起来更像c1 c2E / V，因为's some baseline amount of work done per node (setting up loops, checking basic conditions, etc.), which is what'占了通过c1项，加上与所访问的边数成比例的一些工作量（E / V，每个边缘完成的工作次数） . 如果我们乘以V，我们就可以得到
4 回答
我希望这对于理解广度优先搜索a.k.a BFS的计算时间复杂度有困难的任何人都有帮助 .
时间复杂度如下：
我试图简化代码和复杂度计算，但如果您有任何问题，请告诉我 .
这里的其他答案可以很好地展示BFS如何运行以及如何分析它 . 我想重新审视您原来的数学分析，以显示您的推理在哪里给出的估计值低于真实值 .
你的分析是这样的：
设N是入射到每个节点的平均边数（N = E / V） .
因此，每个节点花费O（N）时间对队列进行操作 .
由于存在V个节点，因此总运行时间为O（V）·O（N）= O（V）·O（E / V）= O（E） .
你非常接近在这里做出正确的估计 . 问题是缺少的V术语来自何处 . 这里的问题是，奇怪的是，你不能说O（V）·O（E / V）= O（E） .
你完全正确的是每个节点的平均工作量是O（E / V） . 这意味着，通过E / V的某个倍数，从上面开始完成总工作量 . 如果我们考虑BFS实际在做什么，每个节点完成的工作可能看起来更像c1 c2E / V，因为's some baseline amount of work done per node (setting up loops, checking basic conditions, etc.), which is what'占了通过c1项，加上与所访问的边数成比例的一些工作量（E / V，每个边缘完成的工作次数） . 如果我们乘以V，我们就可以得到
这里发生的事情是，那些可以让我们忽略的那些可爱的低阶术语在这里实际上很重要，所以我们不能轻易丢弃它们 . 所以这至少是在数学上发生了什么 .
这里实际发生的是，无论图中有多少边，都有's some baseline amount of work you have to do for each node independently of those edges. That' s设置来执行诸如运行核心if语句，设置局部变量等 .
执行
O(1)操作L次，结果为O(L)复杂度 . 因此，从队列中删除和添加顶点是O（1），但是当你为V顶点执行此操作时，会得到O(V)复杂度 . 因此，O(V) + O(E) = O(V+E)考虑以下图表，我们看到时间复杂度如何是O（| V | | E |）而不是O（V * E） .
邻接名单
操作BFS如何逐步工作
步骤1：
邻接列表：
第2步：
邻接列表：
第三步：
邻接列表：
第4步：
邻接列表：
第五步：
邻接列表：
第六步：
邻接列表：
总步数：
假设邻接列表表示，V是顶点数，E是边数 .
每个顶点最多排队并出列一次 .
扫描所有相邻顶点需要 O(|E|) 时间，因为邻接列表的长度总和为 |E| .
因此，BFS的时间复杂性给出了时间复杂度 .