Как выглядит Big-O Depth-First-Search = O(V+E)?

Question

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

DFS(G, t)
{

1   stack S = new empty Stack of size G.|V|  ... O(1)
2   S.push(t)                                ... O(1)

3   while(S is not Empty)                    ... O(|V|), this will always be =<|V|
    {
4       u = S.pop()                          ... O(1)

5       if(u.visited = false)                ... O(1)
        {
6            u.visited = true                ... O(1)

7            for-each edge (u,v) in G.E      ... O(|E|), this will always be =<|E|
8                if(v.visited = false)       ... O(1)
9                    S.push(v)               ... O(1)
        }
    }
}

Теперь объединяя сложность каждой строки, мы имеем:

O (1) + O (1) + O (| V |) [O (1) + O (1) + O (1) + O (E) [O (1) + O (1)]] = O (2) + O (V) + O (V) + O (V) + O (V) + O (V * E) + O (V * E) = 4 * O (V) + 2 * O (V) * E) = O(V * E)

Я не получил O(V+E)? Может кто-нибудь показать мне математически, как мы достигаем O(V+E)?

Кто-нибудь может дать понимание?

Answer 1

Давайте сделаем это просто.

Внешний цикл, он только зацикливается на S один раз, удаляя каждый элемент, который он видит. таким образом O(|V|) в вашей записи.

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

Однако это не для каждого элемента S Вы удаляете каждый край. Вы удаляете все узлы и все ребра, таким образом O(|V|+|E|),

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