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

В общем случае время выполнения поиска в глубину следующее. Оба цикла в dfs выполняются за \(O(V)\) (без учёта происходящего в dfsvisit), поскольку они вычисляются по одному разу для каждой вершины графа. Цикл в dfsvisit вычисляется один раз для каждого ребра из списка смежности текущей вершины. Поскольку dfsvisit вызывается рекурсивно только в том случае, если вершина окрашена в белый, то цикл для каждого ребра графа выполнится максимум единожды (\(O(E)\)). Таким образом, общее время выполнения поиска в глубину равно \(O(V + E)\).