그래프의 탐색은 하나의 정점에서 시작하여 그래프의 모드 정점들을 한 번씩 방문하는 것이 목적이다. 그래프의 데이터는 배열처럼 정렬이 되어 있지 않기 때문에 원하는 자료를 찾으려면, 하나씩 모두 방문하여 찾아야 한다.

BFS(Breadth-First Search)

---

1. 한국을 기준으로 미국까지 가는 방법을 가까운 정점부터 탐색한다.
2. 그리고 더는 탐색할 정점이 없을 때, 그다음 떨어져 있는 정점을 순서대로 방문한다.

직항이라면 한국과 미국 사이에 어떠한 경유지도 없기 때문에 제일 가까운 정점에 미국이 있고, 경유지가 있다면 직항보다 거리가 멀다는 사실을 확인할 수 있다.

이렇게, 너비를 우선적으로 탐색하는 방법을 Breadth-First Search, 너비 우선 탐색이라고 하고, 주로 두 정점 사이의 최단 경로를 찾을 때 사용한다. 만약, 경로를 하나씩 전부 방문한다면, 최악의 경우에는 모든 경로를 다 살펴봐야 한다.

DFS(Depth-First Search)

---