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

Question

Я пытаюсь понять временную сложность некоторых эффективных методов обнаружения циклов в графе.

Здесь объясняется два подхода . Я бы предположил, что временная сложность обеспечивается в наихудшем случае.
Первый - это поиск объединения, который, как говорят, имеет временную сложность O (Vlog E).
Второй использует подход, основанный на DFS и, как говорят, имеет временную сложность O (V + E). Если я прав, это асимптотически более эффективная сложность, чем O (Vlog E). Также удобно, что подход, основанный на DFS, можно использовать для ориентированных и неориентированных графов.

Моя проблема в том, что я не вижу, как можно считать, что второй подход выполняется за время O (V + E), потому что DFS выполняется за время O (V + E), а алгоритм проверяет узлы, смежные с любые обнаруженные узлы для начального узла. Конечно, это будет означать, что алгоритм выполняется за время O (V ² ), потому что до V-1 смежных узлов, возможно, придется пройти через каждый обнаруженный узел? Очевидно, что более чем одному узлу невозможно требовать обхода n-1 смежных узлов, но, насколько я понимаю, это все равно будет верхняя граница времени выполнения.

Надеюсь, кто-то понимает, почему я так думаю, и может помочь мне понять, почему сложность O (V + E).

Answer 1

Алгоритм, основанный на DFS, обычно поддерживает «посещенную» логическую переменную для каждой вершины, которая содержит один бит информации - эта вершина уже была посещена или нет. Таким образом, ни одна из вершин не может быть посещена более одного раза.

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

Запуск DFS из всех вершин графа необходим в случае, когда граф состоит из нескольких соединенных компонентов - логическая переменная «посещения» гарантирует, что DFS не будет проходите один и тот же компонент снова и снова.