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

Прежде, чем перейти к другим алгоритмам для графов, давайте проанализируем временнУю производительность поиска в ширину. В первую очередь нужно заметить, что для каждой вершины из \(|V|\) происходит как минимум одно вычисление цикла while. Вы можете убедиться, что это так, поскольку вершина должна быть окрашена в белый перед тем, как быть проверенной и добавленной в очередь. Это даёт нам \(O(V)\) для цикла while. Вложенный цикл for вычисляется минимум один раз для каждого ребра из \(|E|\). Причина этого в том, что каждая вершина (например, \(u\)) хотя бы единожды извлекается из очереди, и мы проверяем ребро из \(u\) в \(v\) только в этом случае. Это даёт \(O(E)\) для каждого цикла for. Комбинируя два цикла вместе, получим \(O(V + E)\).

Конечно, поиск в ширину - всего лишь часть задания. Проследовать по ссылкам от стартового узла до целевого является его второй частью. Наихудшим случаем станет граф в виде обычной длинной цепочки. Тогда проход по всем вершинам даст \(O(V)\). Обычно же берётся некая часть \(|V|\), но мы по-прежнему будем писать \(O(V)\).

Наконец, для данной задачи потребуется время на постороение начального графа. Мы оставляем анализ функции buildGraph в качестве упражнения для вас.