Временная сложность поиска в глубину с задними краями

Я новичок в DFS и только что узнал, что временная сложность DFS будет O (V + E) при использовании списка смежности. Мне было интересно, какова была бы временная сложность DFS, если бы были включены обратные края, поскольку обратные края требуют, чтобы поиск возвращался к ранее обнаруженным узлам.

Я пытался найти это в Интернете, но я не могу найти хороший ответ на этот вопрос.


graph traversal depth-first-search
person Edward    schedule 26.05.2021    source источник
comment
Какие источники вы нашли, в которых говорится, что это только O (V + E), когда нет задних ребер?   -  person kaya3    schedule 26.05.2021
comment
stackoverflow.com/questions/11468621/ я предположил, что это применимо к DFS в целом, но мне было интересно, какова была бы временная сложность, если бы были включены задние края   -  person Edward    schedule 27.05.2021
comment
Во втором ответе на этот вопрос явно упоминаются задние края: stackoverflow.com/a/11468703/12299000 Ожидаются задние края как нормальная часть алгоритма DFS любое обсуждение его сложности должно касаться случая, когда есть обратные ребра.   -  person kaya3    schedule 27.05.2021