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

Подсчитаем общее число операций при выполнении процедуры 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).