DFS를 실행시키는 데 시간이 얼마나 걸리는지 알아보자.

총 Node의 수를 V

엣지의 수를 E 라고 하자.

DFS 알고리즘

(처음에 모든 노드를 방문하지 않았다고 표시)

시작점 노드를 옅은 회색 표시 후, 스택에 넣는다

스택에 아무 노드도 없을 때까지:

1. 스택에서 가장 위 노드를 꺼냅니다
2. 짙은 회색(방문 처리) 표시를 합니다
3. 이 노드에 인접해 있는 노드들을 돌면서:
    1. 노란색 노드면:
        1. 옅은 회색으로 표시한다
        2. 스택에 넣는다

DFS Node 전처리

먼저 모든 Node를 노란색 Node로 표시하는 데는 V의 시간이 걸린다.

모든 Node를 다 돌면서 일일히 노란색으로 만들어야 되기 때문이다.

(DFS를 할 때 노란색 Node는 아예 처음보는 Node, 옅은 회색은 스택에 들어있는 Node, 짙은 회색은 방문한 Node로 처리했다.)

Node들 전처리는 O(V)가 걸린다고 할 수 있다.

스택에 Node를 넣고 빼는 데 걸리는 시간

BFS를 할 때 큐에 같은 Node가 두 번 들어갈 수 없었던 것처럼, DFS를 할 때도 스택에 같은 Node가 두번 들어갈 수 없다.

꺼낸 Node를 돌 때 회색인 Node들은 (이미 방문했거나 스택에 있는 Node들) 무시해주기 때문이다.

스택은 더블리 링크드 리스트를 사용하면 맨 뒤에 삽입하고 맨 뒤에 있는 데이터를 꺼내오는 연산들은 O(1)로 할 수 있다

최대 V 개의 Node 들이 스택에 들어갔다 나온다.

Node들이 스택에 들어갔다 나오는데 걸리는 총 시간은 O(V)라고 할 수 있다.

스택에서 뺀 Node들의 인접한 Node들을 도는데 걸리는 시간

스택에서 Node를 꺼낼 때마다, Node에 인접한 다른 Node들을 돈다.

이 부분은 다 합치면 얼마나 걸리까?

위에서 얘기했듯이 모든 Node는 스택에 한 번만 들어가서 한 번만 나올 수 있다.

Node가 한 번 나올 때마다 그 Node의 인접 리스트를 돈다.

그러니까 모든 Node들의 인접 리스트를 딱 한번만 돈다고 할 수 있다.

총 엣지 수가 E니까 이 단계도 총 E에 비례하는 만큼 실행된다고 할 수 있다.

스택에서 뺀 Node들의 인접한 Node들을 도는데 O(E) 가 걸린다.

정리

DFS의 여러 단계들이 걸리는 시간들을 다 합쳐보자.

전처리 : O(V)

스택에서 Node 넣고 빼기 : O(V)

인접한 Node들을 도는데 걸리는 시간 : O(E)

이걸 다 더해보면 O(2V + E)인데, 앞에 2는 무시해도 되니까 총 O(V + E)의 시간 복잡도가 걸린다고 할 수 있다.