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

 

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