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

Question

遍历顶点的每个相邻边的时间复杂度称为O(N)，其中N是相邻边的数量。因此，对于V个顶点，时间复杂度变为O(V*N)=
O(E)，其中E是图形中边的总数。由于是从Queue中删除顶点或向Queue中添加顶点O(1)，因此为什么将顶点添加到BFS的整体时间复杂度中O(V+E)。

Answer 1

我希望这对任何难以理解“广度优先搜索”（又称为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

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