[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를 방문한다. 

B노드를 방문하면 이미 A노드 방문시, B의 인접노드를 모두 방문했으므로, 넘어간다.

C노드를 방문하면 이미 A노드 방문시, C의 인접노드를 모두 방문했으므로, 넘어간다.

D노드를 방문하면 이미 A노드 방문시, D의 인접노드를 모두 방문했으므로, 넘어간다.

E노드를 방문하면 이미 A노드 방문시, E의 인접노드를 모두 방문했으므로, 넘어간다.

 

F노드를 방문하면 인접한 노드 H, G를 방문한다.

H노드를 방문하면 이미 F노드 방문시, H의 인접노드를 모두 방문했으므로, 넘어간다. 

G노드를 방문하면 이미 F노드 방문시, G의 인접노드를 모두 방문했으므로, 넘어간다.

 

A 노드에서 G노드까지 총 8개의 노드를 방문할때, O(N)

이미 방문한 인접한 노드는 방문 안하므로, 간선의 개수만큼만 방문한다. O(N+E)