연결 리스트로 구현된 그래프의 깊이 우선 탐색 시 시간복잡도가 O(V+E)인 이유는 무엇인가요?

Question

0

싫어요

           A
         / | \
        B  |  D -- E
         \ | /     |
           C ------+

연결 리스트로 구현된 어떤 그래프가 있다고 할 때, n개의 정점을 방문하기 위해 DFS 함수를 n번 호출해야 하고, 매 호출 시마다 다음으로 방문할 정점을 찾기 위해 일정횟수 이상 연결 리스트의 노드 사이를 이동해야 합니다.

이 노드 이동횟수를 m번이라고 하면, 시간 복잡도는 O(nm)이 되어야 할 것 같은데..실제로는 정점의 개수 V와 간선의 개수 E를 더한 O(V+E)입니다.

어떻게 해서 O(V+E)가 계산된 건가요?

score 2 · Accepted Answer

노드의 개수 N = 정점의 개수 V 이고, 이동횟수가 곧 간선(edge)의 개수이므로, O(V+E) 가 됩니다. O(nm) 은 n과 m 의 루프가 중첩된 것을 의미합니다.


for(int i=0; i<N; i++)
{
    for(int j=0; j<M; j++)
    {
       // do something
    }
 }