我希望这对任何难以理解“广度优先搜索”(又称为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
我试图简化代码和复杂度计算,但是如果您有任何问题,请告诉我。