[알고리즘] BFS와 DFS 시간복잡도

BFS는 도착지점까지 최단거리를 구할 때 유리하다. (너비 우선 탐색)

 

DFS는 도착지점까지 갈 수 있는 모든 경로를 봐야할 때 유리하다. (깊이 우선 탐색)

각각의 경로의 특징을 저장할 수 있다.

 

모든 지점을 방문해야 한다면 BFS, DFS의 시간복잡도는 동일하다.

인접리스트: O(N+E)

인접행렬: O(N*N)

 

하지만 DFS를 재귀함수로 구현 한다는 점에서

실제 수행시간은 DFS보다 BFS가 조금 더 빠르게 동작한다.