BFS, DFS의 적합한 사용

코딩 테스트를 위한 자료 구조와 알고리즘 with C++

 

 

두 탐색의 시간 복잡도는 O(V + E)로 같다.

 

BFS

시작 정점에서 가까운 정점을 찾는 데 적합하다.
특정 정점을 탐색할 경우 최단 거리 경로를 보장한다.
탐색 시 생성된 검색 트리는 짧고 넓으며 많은 메모리를 필요로 한다.
상대적으로 코드 크기가 커 명령어 캐시 적중률이 낮다.

 

DFS

시작 정점에서 먼 정점을 찾는 데 적합하다.
특정 정점 탐색 시 최단 경로를 보장하지 않는다.
탐색 시 생성된 검색 트리는 길고 좁으며 상대적으로 적은 메모리를 사용한다.
상대적으로 코드 크기가 작아 명령어 캐시 적중률이 높다.