5.2.2 Анализ поиска в ширину

Оценим время работы описанной процедуры. В процессе работы вершины только темнеют, так что каждая вершина кладётся в очередь не более одного раза (благодаря проверке в строке 12). Следовательно, и вынуть её можно только один раз. Каждая операция с очередью требует O (1) шагов, так что всего на операции с очередью уходит время O(V). Теперь заметим, что список смежных вершин просматривается, лишь когда вершина извлекается из очереди, то есть не более одного раза. Сумма длин всех этих списков равна |Е| (2|Е| для неориентированного графа) и всего на их обработку уйдёт время O(Е). Инициализация требует O(V) шагов, так что всего полу- чается O(V + Е). Тем самым время работы процедуры BFS пропорционально размеру представления графа G в виде списков смежных вершин.

Поиск в ширину для полного обхода графа с n вершинами и m дугами требует столько же времени, как и поиск в глубину, то есть времени порядка O(max(n, m)). Поскольку обычно m  n, то получается O(m).