Как описать сложность расчета глубины графика DFS?

Ну, тут все просто - для каждого ребра выполняется некоторая (конкретная) работа O(1), так что имеем O(n), где n - количество ребер графа...