BFS / DFS

그래프의 정점 탐색 방법중 대표적인 방법이 BFS와 DFS이다. 둘다 탐색 순서만 다를 뿐 모든 자료를 하나씩 확인해 본다는 점은 같다.

BFS(Breadth-First Search,너비 우선 탐색)

한국에서 미국을 간다고 한다면, 한국에서 미국까지 가는 방법을 가까운 정점부터 탐색한다. 탐색할 정점이 없을때는 그 다음 떨어져 있는 정점을 순회한다.(경유)

주로 두 정점 사이의 최단 경로를 찾고 싶을때 사용한다. 만약, 경로를 하나씩 전부 방문하는 방식으로 하게 된다면, 최악의 경우에는 모든 경로를 다 살펴보게 될지도 모른다.

DFS(Depth-First Search,깊이 우선 탐색)

어떤 경로가 미국으로 가는지 모르기 때문에 하나의 경로를 끝까지 탐색한 후, 미국 도착이 아니면 다음 경로로 넘어간다. 운이 좋다면 몇 번만에 경로를 찾을 수 있다. DFS는 한 경로를 완벽하게 탐하지만, 최단경로를 찾기에는 좋지 않다.

BFS : 최단경로를 찾을 수 있음.
DFS : 한 경로를 완벽하게 탐색.
만약, 그래프의 규모가 작고 depth가 얕다면 DFS 탐색방법이 더 좋은듯하다! 그반대는 BFS!