Почему временная сложность DFS для обнаружения цикла в неориентированном графе O (| V |), а не O (| V | + | E |)?

Question

Может ли кто-нибудь подробно объяснить мне, почему и как верхняя граница DFS для обнаружения цикла в неориентированном графе равна O (| V |)?

Answer 1

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