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

Question

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

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

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

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

Answer 1

DFS를 V번 호출해서 V가 되고, (돌아가는 것까지 하면 2V이지만 빅오 표기이므로 2를 생략합니다.)

각 호출에서 그 노드와 간선으로 연결된 노드를 이미 방문했는지 확인해서 E입니다.

여기서 E인 이유가 의문인가요? 각 간선은 노드 두 개에만 연결됩니다! (2E이지만 빅오 표기이므로 2 생략)

더하면 O(V+E)가 됩니다.