Анализ поиска в глубину

Подсчитаем общее число операций при выполнении процедуры DFS. Цик-
лы в строках 1 – 3 и 5 – 7 требуют (V) времени (помимо вызовов DFS-VISIT).
Процедура DFS-VISIT вызывается ровно один раз для каждой вершины (ей
передаётся белая вершина, и она сразу же делает её серой). Во время выполнения
DFS-VISIT(v) цикл в строках 3 – 6 выполняется | Adj [ v ]| раз. Поскольку

общее время выполнения строк 3 – 6 процедуры DFS-VISIT составляет (Е). В сумме получается время (V + E).

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