그래프의 탐색은 하나의 정점에서 시작하여 그래프의 모든 정점들을 한 번씩 방문(탐색)하는 것이 목적입니다. 그래프의 데이터는 배열처럼 정렬이 되어 있지 않습니다. 그래서 원하는 자료를 찾으려면, 하나씩 모두 방문하여 찾아야 합니다.
지하철 노선도를 보여주는 애플리케이션에서 경로를 탐색할 때에는, 최단 경로나 최소 환승 등 하나의 목적에도 여러가지 방법이 있습니다. 이처럼 그래프의 모든 정점 탐색 방법에도 여러 가지가 있습니다. 그중에서 가장 대표적인 두 가지 방법, DFS와 BFS를 소개합니다. 이 둘은 데이터를 탐색하는 순서만 다를 뿐, 모든 자료를 하나씩 확인해 본다는 점은 같습니다.
BFS (Breadth-First Search), 너비 우선 탐색
가까운 정점부터 탐색합니다. 그리고 더는 탐색할 정점이 없을 때, 그 다음 떨어져 있는 정점을 순서대로 방문합니다. 이렇게 너비를 우선적으로 탐색하는 방법을 Breadth-First Search, 너비 우선 탐색이라고 합니다. 주로 두 정점 사이의 최단 경로를 찾을 때 사용합니다. 만약, 경로를 하나씩 전부 방문한다면, 최악의 경우에는 모든 경로를 다 살펴보아야 합니다.
DFS (Depth-First Search), 깊이 우선 탐색
하나의 경로를 끝까지 탐색한 후, 찾는 곳이 아니라면 다음 경로로 넘어가 탐색합니다. 하나의 노선을 끝까지 들어가서 확인하고 다음을 넘어가기 때문에, 운이 좋다면 단 몇 번만에 경로를 찾을 수 있습니다. 또 찾는 곳이 아님을 미리 체크할 수 있다면, 바로 그 순간 다음 탐색으로 넘어갈 수 있습니다. 이렇게 깊이를 우선적으로 탐색하는 방법을 Depth-First Search, 깊이 우선 탐색이라고 합니다. 한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용합니다. BFS보다 탐색 시간은 조금 오래 걸릴지라도 모든 노드를 완전히 탐색할 수 있습니다. 만약, BFS로 탐색을 하게 된다면 제일 첫 번째 경로가 찾는 경로여도 다른 모든 경로를 살펴보아야 합니다.
DFS와 BFS는 모든 정점을 한 번만 방문한다는 공통점을 가지고 있지만, 사용할 때의 장단점은 분명하기 때문에 해당 상황에 맞는 탐색 기법을 사용해야 합니다.
