BFS, DFS

그래프의 탐색은 하나의 정점에서 시작하여 그래프의 모든 정점을 한번씩 방문(탐색)하는 것이 목적이다.
정점 탐색방법의 대표적인 두가지는 BFS와 DFS가 있다.
이 둘은 데이터를 탐색하는 순서만 다를뿐, 모든 자료를 하나씩 확인해 본다는 점은 같다.

DFS와 BFS는 모든 정점을 한 번만 방문한다는 공통점을 가지고 있지만, 사용할때의 장단점은 분명하기 때문에 해당하는 상황에 맞는 탐색 기법을 사용해야 한다.

---

BFS(Breadth-First Search)

-너비를 먼저 탐색하는 방법이다. 너비 우선 탐색이라고 한다.
-최단경로(주로 두 정점 사이의 최단 경로를 찾을때 사용한다.)
-한 경로를 끝까지 모두 다 탐색하는 처음 발견한 답이 최단 거리가 아닐 수 있지만, BFS는 현재 있는 노드에서 가까운 곳부터 탐색하므로 경로를 탐색하는 도중 가장 먼저 발견한 해답이 최단거리라는 보장이 된다.
-가까운 정점부터 탐색한다. 같은 레벨까지만. 그리고 더는 탐색할 정점이 없을때, 그 다음 레벨에 위치한 정점을 순서대로 방문한다.

 

 

DFS(Depth-First Search)

-깊이를 먼저 탐색하는 방법이다. 깊이 우선 탐색이라고 한다.
-한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할때 사용한다.(하나의 경로를 끝까지 탐색한후, 다음경로로 넘어가 탐색한다.)
-BFS보다 탐색 시간은 조금 오래 걸릴지라도 모든 노드를 완전히 탐색할수있다.

---

출처

코드스테이츠