[Algorithm] DFS, BFS 시간복잡도가 O(N+E)인 이유

 

 

노드의 개수가 N이고 간선의 개수가 E일 때,

DFS, BFS로 그래프를 완전탐색한다면 시간복잡도가 O(N+E)인 이유는 무엇일까?

 

 

 

그래프 예시

 

 

 

 

DFS, BFS는 완전탐색에 이용된다.

반복문으로 모든 노드를 탐색해야 하므로 시간복잡도는 최대 O(N)을 갖는다. 

 

그럼 이제 노드 하나를 방문해보자.

여기서 부터 간선의 개수가 연산에 영향을 미친다.

 

DFS는 재귀호출로 인접한 노드에 접근하고

BFS는 인접한 노드를 큐에 넣는다. 

 

그러므로

 

DFS는 인접한 노드의 개수, 즉 간선의 개수에 따라 재귀호출이 반복되고

BFS는 인접한 노드의 개수, 즉 간선의 개수에 따라 while문이 반복된다. ( 큐가 빌때 까지 )

 

그리고

여기서 방문처리가 이루어 진다. 

 

A노드를 방문하면 인접한 노드 B, C를 방문하고 B를 방문하면 인접한 노드 E,D를 방문한다. 그러면 노드A를 기점으로 한 탐색이 끝나고 노드B, 노드C ...를 기점으로 탐색을 진행할 때, A가 방문한 B, C, E, D를 방문하지 않아도 되므로, 추가적인 재귀호출과 while문 연산을 발생하지 않는다. 위 그래프는 A노드를 방문했을 때 4번 연산, F 노드를 방문했을 때, 2번 연산하므로, 8개 노드를 완전탐색 했을 때, 총 6번 연산하게 된다. 

 

결국, 간선의 개수만큼만 재귀호출과 while문 연산이 일어나므로 N개의 노드를 완전탐색 했을 때, 발생하는 연산의 개수는 E개가 된다. 그러므로 시간복잡도는 O(N + E)이다.