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

  • Z时代
  • 2024-01-10
  • 分类：问答

遍历顶点的每个相邻边的时间复杂度称为O(N)，其中N是相邻边的数量。因此，对于V个顶点，时间复杂度变为O(V*N)=

O(E)，其中E是图形中边的总数。由于是从Queue中删除顶点或向Queue中添加顶点O(1)，因此为什么将顶点添加到BFS的整体时间复杂度中O(V+E)。

回答：

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

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

以上是 广度优先搜索时间复杂度分析 的全部内容， 来源链接： utcz.com/qa/435328.html

回到顶部