广度优先搜索时间复杂度分析 [英] Breadth First Search time complexity analysis

问题描述

在顶点的每个相邻边上的时间复杂度是 O（N），其中N是相邻边的数量。因此，对于V个顶点，时间复杂度变为 O（V * N） = O（E），其中E是图中边的总数。由于从/到队列中删除和添加一个顶点是 O（1），为什么它被添加到BFS的总体时间复杂度为 O（V + E）。

解决方案

我希望这有助于任何人理解计算时间复杂性广度优先搜索aka BFS。

 队列graphTraversal.add（firstVertex）; 
 
 //这个while循环将运行V次，其中V是图中顶点的总数。 
 while（graphTraversal.isEmpty == false）
 
 currentVertex = graphTraversal.getVertex（）; 
 
 //这个while循环将运行Eaj次，其中Eaj是当前顶点的相邻边的数量。 
 while（currentVertex.hasAdjacentVertices）
 graphTraversal.add（adjacentVertex）; 
 
 graphTraversal.remove（currentVertex）; 
  

时间复杂度如下：

<$ p （1）+ Eaj + O（1））
V + V * Eaj + V
2V + E（图中边的总数）
V + E

我试图简化代码和复杂性计算，但如果你有任何问题让我知道。

Time complexity to go over each adjacent edges of a vertex is say O(N), where N is number of adjacent edges. So for V number of vertices time complexity becomes O(V*N) = O(E), where E is the total number of edges in the graph. Since removing and adding a vertex from/to Queue is O(1), why it is added to the overall time complexity of BFS as O(V+E).

解决方案

I hope this is helpful to anybody having trouble understanding computational time complexity for Breadth First Search a.k.a 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);

Time complexity is as follows:

V * (O(1) + Eaj + O(1))
V + V * Eaj + V
2V + E(total number of edges in graph)
V + E

I have tried to simplify the code and complexity computation but still if you have any questions let me know.

这篇关于广度优先搜索时间复杂度分析的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！