[알고리즘]BFS/DFS

그래프는 배열처럼 정렬이 되어있지 않기 때문에 원하는 자료를 찾으려면 하나씩 탐색해서 찾아야 한다.

그래프의 모든 정점 탐색 방법에는 대표적으로 BFS와 DFS가 있다.
이 둘은 데이터를 탐색하는 순서만 다를 뿐, 모든 자료를 확인해 본다는 점은 동일하다.

BFS(Breadth-First Search)

가까운 정점부터 탐색한다. 그리고 더는 탐색할 정점이 없을 때, 그 다음 떨어져있는 정점을 탐색한다.
이렇게, 너비를 우선적으로 탐색하는 방법을 너비 우선 탐색(Breadth-First Search)이라고 한다. 주로 두 정점 사이의 최단 경로를 찾을 때 사용하고, 만약 경로를 하나씩 전부 방문한다면, 최악의 경우에는 모든 경로를 다 살펴보아야 한다.

DFS(Depth-First Search)

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