广度优先搜索时间复杂度分析

Question

遍历顶点的每个相邻边的时间复杂度是，例如，O（N），其中N是相邻边的数量。因此，对于V顶点数，时间复杂度变为O（V*N）=O（E），其中E是图中的边总数。既然从队列中移除和添加顶点是O（1），为什么它会作为O（ve）添加到BFS的总体时间复杂度中？

Answer 1

这里的其他答案很好地展示了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实际上在做什么，每个节点完成的功可能更像c₁c₂E/V，因为每个节点完成的功有一些基线量（设置循环、检查基本条件等），这是由c₁项解释的，加上与访问的边数成比例的工作量（E/V，乘以每条边完成的工作量）。如果我们把这个乘以V，我们就得到了

V·（c₁c₂E/V）

=c₁V c₂E

=Θ（V E）

这里发生的事情是，这些可爱的低阶项，大O很方便地让我们忽略，实际上在这里很重要，所以我们不能轻易丢弃它们。所以至少在数学上是这样的。

这里实际发生的是，不管图中有多少条边，每个节点都必须独立于这些边做一些基线工作量。这就是运行核心if语句、设置局部变量等操作的设置。

Answer 2

考虑下面的图，我们可以看到时间复杂度是O（|V||E|），但不是O（V*E）。

邻接表

V     E
v0:{v1,v2} 
v1:{v3}
v2:{v3}
v3:{}

如何一步一步地操作BFS

第一步：

邻接列表：

V     E
v0: {v1,v2} mark, enqueue v0
v1: {v3}
v2: {v3}
v3: {}

第二步：

邻接列表：

V     E
v0: {v1,v2} dequeue v0;mark, enqueue v1,v2
v1: {v3}
v2: {v3}
v3: {}

第三步：

邻接列表：

V     E
v0: {v1,v2}
v1: {v3} dequeue v1; mark,enqueue v3
v2: {v3}
v3: {}

第四步：

邻接列表：

V     E
v0: {v1,v2}
v1: {v3}
v2: {v3} dequeue v2, check its adjacency list (v3 already marked)
v3: {}

第五步：

邻接列表：

V     E
v0: {v1,v2}
v1: {v3}
v2: {v3}
v3: {} dequeue v3; check its adjacency list

第六步：

邻接列表：

V     E
v0: {v1,v2} |E0|=2
v1: {v3}    |E1|=1
v2: {v3}    |E2|=1
v3: {}      |E3|=0

总步骤数：

|V| + |E0| + |E1| + |E2| +|E3| == |V|+|E|
 4  +  2   +  1   +   1  + 0   ==  4 + 4
                           8   ==  8

假设采用邻接列表表示，V是顶点数，E是边数。

每个顶点最多排队一次。

扫描所有相邻顶点需要O（|E |）时间，因为邻接列表的长度之和是|E |。

因此，BFS的时间复杂度为aO（|V | | E |）时间复杂度。

Answer 3

我希望这对理解广度优先搜索（又名BFS）的计算时间复杂度有困难的人有所帮助。

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

我试图简化代码和复杂度计算，但如果你有任何问题，请告诉我。