그래프의 각 꼭지점, 즉 vertex라고 하는 이 정점을 탐색하는 데엔 여러 방법이 있다.

그래프를 탐색한다는 것은 모든 정점들을 한번 씩 방문하여 데이터를 탐색한다는 말이다.
그런데 그래프의 데이터는 배열처럼 정렬이 안되어있기 때문에 원하는 자료를 찾기 위해서는 모든 정점을 빠짐없이 탐색해야 한다.

그래프를 탐색하는 방법 중 가장 대표적인 것은 DFS와 BFS다.
이름이 비슷해서 자주 헷갈리는 이 두 친구는 이름만큼이나 하는 일도 같다.
모든 자료를 하나씩 확인해 본다는 점이다.

다만 다른점은, 데이터를 탐색하는 순서가 다르다는 것임을 기억하자.

BFS(Breadth-First Search)

주로 BFS는 최단경로를 찾기 위해 사용하는 경우가 많다.

예를 들어 한국에서 미국으로 가는 최단경로의 비행기 티켓을 끊으려고 한다. 그렇다면 어떻게 최단경로를 찾을 수 있을까?

정답은! BFS(너비 우선 탐색)이다.

한국(root,최 상단의 부모노드)을 기준으로 가장 가까운 정점을 탐색한다. (여기서는 중국, 터키, 일본, 괌이 되겠다.) 여기서 미국을 찾지 못하면 그 다음 떨어져있는 정점을 순서대로 탐색한다.

아마도 이 예시에서는 한국-터키-미국이 될 것이다.

DFS(Depth-First Search)

그렇다면 한국에서 미국으로 가는 방법에는 몇가지가 있을까?

우리가 찾고싶은 정보는 최종목적지가 미국이기 때문에 모든 경로를 순서대로 끝까지 탐색을 해야만 도착지가 미국인지, 아닌지를 알 수 있을 것이다.

이처럼 DFS는 하나의 경로를 끝까지 탐색한 후, 미국이 아니라면 다음경로로 넘어가는 탐색방법이다.
DFS는 깊이를 우선적으로 탐색하기 때문에 Depth-우선탐색이라는 이름이 붙여졌다.

• BFS(너비 우선 탐색)는 최단거리를 찾을 때, depth가 얕을 때 주로 사용하는 것이 효율적이다.
• DFS(깊이 우선 탐색)는 탐색시간은 오래걸리지만 모든 노드를 완전히 탐색할 수 있어서 모든경로를 확인해야 할때 사용된다.