그래프의 탐색

• 모든 정점을 한번씩 방문하는 것이 목적

BFS(Breathed-First Search)

• 가장 가까운 정점부터 탐색한다.
• 더 탐색할 정점이 없으면 그 다음 떨어져 있는 정점을 방문한다.
• 너비를 우선적으로 탐색하는 방법이다. (너비 우선 탐색)
  • 최단 경로를 찾는데 사용된다.
  • 최악의 경우 모든 경로를 탐색해야한다.
• 보통 큐로 구현함

DFS(Depth-First Search)

• 하나의 경로를 끝까지 탐색하고 조건에 맞지 않으면 다음 경로를 탐색한다.
• 깊이 우선 탐색이다.
  • BFS보다 수행시간은 오래걸릴 수 있지만 노드를 완전히 방문할 수 있다.
• 보통 스택(재귀)으로 구현함