在初始化时，广度优先搜索会对所有顶点的信息进行更新，因此初始化的开销是O(V)。当一个顶点第一次被访问（染为灰色）时，将它放入队列，顶点不会重复添加。因为队列能够在常数时间添加或者删除元素，所以管理队列的开销是O(V)。最后，每一个顶点都仅仅会从队列中删除一次，当且仅当其所有邻接顶点被访问时。循环处理边的总次数上限为边的总数，即O(E)。因此总开销是O(V+E)。