Сложность рекурсивного DFS

Question

Так что, надеюсь, это простой вопрос, но я не могу найти ответ. Сложность времени DFS, как утверждается, O(|V|+|E|). Теперь у меня возникают проблемы с тем, почему это зависит от количества ребер. Обычное объяснение, которое я видел, выглядит следующим образом:

Скажем, мы реализуем DFS с использованием явного стека (для простоты). Скажем, у нас есть график, где каждый узел соединен со всем остальным. Мы начинаем с некоторого узла, посещаем его, а затем нажимаем все его соседи на стек. Теперь мы выкладываем следующий узел и помещаем все его соседи в стек. Повторяем, пока не посетим все узлы.

Давайте сделаем вид, что узел, который находится поверх стека, еще не посещается на каждой итерации (лучший сценарий для этого графика). В этом случае мы посетили все узлы в |V| двигается, но для каждого из них мы толкнули |V|-1 узлов в стеке, что означает, что все ребра в стеке и сложность O(|E|)

Несколько замечаний. Я утверждаю, что сложность МЕНЬШЕ, чем это, поэтому это доказательство, что только смотрит на лучший сценарий для графика наихудшего случая, прекрасно. Я также предполагаю, что |E| всегда больше |V|. На самом деле, я предполагаю, что это O(|V|^2). Это означает, что O(|V|+|E|) и O(|E|) означают то же самое для меня.

Хорошо, теперь вот моя сделка. Что делать, если мы не используем явный стек?

Взрыв здесь обусловлен тем, что мы продолжаем складывать бесполезные узлы, которые никогда не будут обработаны. Что, если мы вместо этого просто рекурсируем? Преимущество состоит в том, что мы можем проверить, выполнены ли мы перед каждым рекурсивным вызовом.

Поскольку явного стека нет, и я все еще посещаю узлы, которых я раньше не видел, я не вижу, как я могу превысить сложность O(|V|).

Answer 1

Взрыв здесь обусловлен тем, что мы продолжаем складывать бесполезные узлы, которые никогда не будут обработаны. Что, если мы вместо этого просто рекурсируем? Преимущество заключается в том, что мы можем проверить, выполнены ли мы перед каждым рекурсивным вызовом.

Эта проверка по-прежнему способствует времени выполнения. Для каждого узла, который вы посещаете, вам нужно увидеть, какой из его соседей по-прежнему нужно посещать, что означает проверку каждого соседнего края.