DFS(Depth-First Search) : 최대한 깊이 내려간 뒤, 더 이상 깊이 갈 곳이 없을 경우 옆으로 이동
특징
1. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다.
2. 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다.
3. 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.
BFS(Breadth-First Search) : 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동
특징
주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택한다.
DFS와 BFS의 장단점
DFS
장점 : 최선의 경우, 가장 빠른 알고리즘이다. '운 좋게' 항상 해에 도달하는 올바른 경로를 선택한다면, DFS가 최소 실행 시간에 해를 갖는다.
단점 : 찾은 해가 최적이 아닐 가능성이 있고, 최악의 경우 가능한 모든 경로를 탐험하고서야 해를 찾으므로 해에 도달하는 데 오랜 시간이 걸린다.
BFS
장점 : 최적의 해를 찾음을 보장한다.
단점 : 최소 실행시간 보다는 오래 걸린다는 것이 거의 확실하다.
✋ 만약 그래프가 굉장히 크다면 어떤 탐색 기법이 유용할까?
그래프가 굉장히 큰 정보들을 가지고 있다면 BFS를 사용해서 해를 찾는게 좋을것이다. 물론 운이 좋아 DFS를 사용해서 찾다 금방 해를 찾을 수도 있지만 그럴 확률은 큰 그래프에선 너무 희박하기 때문이다.
