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

Question

例如,遍历顶点的每个相邻边的时间复杂度O(N),其中N是相邻边的数量.因此,对于V个顶点,时间复杂度变为O(V*N)= O(E),其中E是图中边的总数.由于从队列中删除和添加顶点是O(1),为什么它被添加到BFS的总体时间复杂度中O(V+E).

Answer 1

考虑以下图表,我们看到时间复杂度如何是O(| V | + | E |)而不是O(V*E).

邻接清单

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

操作BFS如何逐步工作

步骤1:

邻接列表:

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

第2步:

邻接列表:

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: {}

第4步:

邻接列表:

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的时间复杂度给出了O(| V | + | E |)时间复杂度.

Answer 2

我希望这对于理解广度优先搜索又称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

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

Answer 3

执行O(1)操作L时间会导致O(L)复杂性.因此,从队列中删除和添加顶点是O(1),但是当你为V顶点执行此操作时,会出现O(V)复杂性.因此,O(V) + O(E) = O(V+E)

Answer 4

这里的其他答案可以很好地展示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).这意味着,所做的总功asympotically从上方E/V的某个倍数为界如果我们想想BFS究竟是干什么,每个节点所做的工作可能看起来更象C ₁ + C ₂ E/V,因为有每个节点完成的工作的一些基线量(设置循环,检查基本条件等),这是何等的由C占₁项,再加上参观成正比的边数一定量的工作(E/V,倍每边完成的工作).如果我们乘以V,我们就可以得到

V·(c ₁ + c ₂ E/V)

= c ₁ V + c ₂ E.

=Θ(V + E)

这里发生的是那些可爱的低阶术语,大O这么方便让我们忽略在这里实际上很重要,所以我们不能轻易丢弃它们.所以这至少是在数学上发生了什么.

什么是真正发生在这里的是,不管有多少边有在图中,有你有独立的那些边缘每个节点都做一些工作的基线量.这就是运行核心if语句,设置局部变量等的设置.